Blog # 32 : Largest Sum of Consecutive Numbers

This is today's problem :

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 = 3, end index = 6)
{4 5 -1 2}


Solution :

A simple linear algorithm will work by keep track of the current subsequence sum. If that
sum ever drops below zero, that subsequence will not contribute to the subsequent maximal subsequence since it would reduce it by adding the negative sum.

#include<iostream>
using namespace std;
int main()
{
int input[10], i, sum = 0, start = -1, end = -1, current = -1, max = -1;//testing for an array of 10 elements
for(i =0;i<10;i++)
      cin>>input[i];
for(i=0; i<10; i++)
{
 sum += input[i];
 if(sum < 0)
 {
        sum = 0;
        current = i+1;
 }
 if(sum > max)
 {
        max = sum;
        start = current;
        end = i;
 }
}
cout << "Start : " << start << " End : " << end << endl<<"Elements are : ";
for(i = start;i <= end;i++)
cout<<input[i]<<" ";
return 0;
}