Tuesday, November 1, 2011

Largest Sum of Consecutive Numbers

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)

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++){
sum += input[i];

if(sum < 0){
sum = 0;
current = i+1;
}

if(sum > *max){
*max = sum;
*start = current;
*end = i;
}
}
}

Complexities :
  •  Time : O(N)
  • Space : O(1)
Acknowledgments :

2 comments:

  1. thats awesome. i learned a lot, useful for my playing on algorithms...
    could 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!

    ReplyDelete
  2. That question does not sound useful since every i,j such that i=j provides a solution.

    ReplyDelete