/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Find the continuous sequence with the largest sum. Return the sum.
Created Data :
Last Modified : 17-07-2013
============================================================================
*/
#include <iostream>
#include <iomanip>
#include <limits>
using namespace std;
static long CalcSubSeqWithMaxSum(int* arr, int len)
{
long maxSum = numeric_limits<long>::min();
int currentSum = 0;
for(int i = 0; i < len; ++i){
currentSum += arr[i];
if(maxSum < currentSum) maxSum = currentSum;
if(currentSum < 0) currentSum = 0;
}
return maxSum;
}
static void DoTest(int arr[], int len)
{
cout << "The arr is " << endl;
for (int i = 0; i < len; ++i){
cout << setw(4) << arr[i];
}
cout << "\nThe largest sum is ";
cout << CalcSubSeqWithMaxSum(arr, len) << endl;
cout << "----------------------" << endl;
}
int main(int argc, char* argv[])
{
int testCase0[] = { 2, -8, 3, -2, 4, -10 };
DoTest(testCase0, sizeof(testCase0)/ sizeof(testCase0[0]));
int testCase1[] = { -2 };
DoTest(testCase1, sizeof(testCase1)/ sizeof(testCase1[0]));
int testCase2[] = { 2 };
DoTest(testCase2, sizeof(testCase2)/ sizeof(testCase2[0]));
int testCase3[] = { 0 };
DoTest(testCase3, sizeof(testCase3)/ sizeof(testCase3[0]));
int testCase4[]= { -2, -8, -3, -2, -4, -10 };
DoTest(testCase4, sizeof(testCase4)/ sizeof(testCase4[0]));
int testCase5[] = { 2, 8, 3, 2, 4, 10 };
DoTest(testCase5, sizeof(testCase5)/ sizeof(testCase5[0]));
return 0;
}
Output
The arr is
2 -8 3 -2 4 -10
The largest sum is 5
----------------------
The arr is
-2
The largest sum is -2
----------------------
The arr is
2
The largest sum is 2
----------------------
The arr is
0
The largest sum is 0
----------------------
The arr is
-2 -8 -3 -2 -4 -10
The largest sum is -2
----------------------
The arr is
2 8 3 2 4 10
The largest sum is 29
----------------------
Press any key to continue . . .
Solution
Question
You are given an array of integers (both positive and negative). Find the continuous sequence with the largest sum. Return the sum.
EXAMPLE
Input: {2, -8, 3, -2, 4, -10}
Output: 5 (i. e. , {3, -2, 4} )