Given an array of N integers (both positive and negative), find the sub-sequence with largest sum.
For ex: Let A = {1 2 -5 4 5 -1 2 -11} then
largest sum is 10 (start index = 4, end index = 7)
{4 5 -1 2} (excluding end index)
{4 5 -1 2} (excluding end index)
Solution :
void largest_consecutive_sum(int input[], int N, int *start, int *end, int *max){
*start = *end = *max = -1;
int current = -1;
int sum = 0;
for(int i=0; i<N; i++){
int current = -1;
int sum = 0;
for(int i=0; i<N; i++){
sum += input[i];
if(sum < 0){
if(sum > *max){
}if(sum < 0){
sum = 0;
current = i+1;
}current = i+1;
if(sum > *max){
*max = sum;
*start = current;
*end = i;
}*start = current;
*end = i;
}
- Time : O(N)
- Space : O(1)
thats awesome. i learned a lot, useful for my playing on algorithms...
ReplyDeletecould u please add another post about minimum (absolute value) consecutive subsequence. by minimum i mean closest to zero. this is the formal def:
given A[1..n] of real numbers(pos. and neg.) find i and j such that abs(A[i]+A[i+1]+...+A[j]) is closest to zero or zero itself!
That question does not sound useful since every i,j such that i=j provides a solution.
ReplyDelete