max sub_sequence - c

max sub_sequence  - c

 

 

/*
 problem:
 	there is a sequence of number,could be positive or negative,
	find out the sub sequence which has max sum,
 
 solution:
 	loop the sequence,
	use maxendinghere to record sum of elements,when sum < 0, set to 0 and go on summation from next element,
	use maxsofar to record the max sum, each time there is a new maxendinghere, compare with it, and update maxsofar if nessary,
	use a struct seq_max_result to record the result, which include sum / start / end,

efficiency:
	time is O(n), every efficient,
	memory is O(1),
 */
#include <stdio.h>

typedef struct {
	int sum,start,end;
} seq_max_result;

seq_max_result * seq_max(int *arr,int len) {
	// start is the start of every maxendinghere
	int maxsofar = 0,maxendinghere=0,i=0,start=0;
	static seq_max_result result = {0,0,0};
	for(i=0;i<len;i++) {
		if(maxendinghere+*(arr+i) < 0) {
			maxendinghere = 0;
			start = i+1;
		} else {
			maxendinghere += *(arr+i);
		}
		if(maxsofar<maxendinghere) {
			maxsofar = maxendinghere;
			result.start = start;
			result.end = i;
		}
	}
	result.sum = maxsofar;
	return &result;
}

int main() {
	int arr[10] = {-6,2,7,9,-5,6,9,-10,3,5};
	seq_max_result *result = seq_max(arr,10);
	result = seq_max(arr,10);
	printf("[%d , %d]: %d\n",result->start,result->end,result->sum);
}