static int Find_Max_Sum_Sub_Sequence(int[] array) { //historical max and corresponding indexes int maxSoFar = 0; int maxStart = 0; int maxEnd = 0; //running max value and the start index of the sub-sequence int curMax = 0; int curMaxStart = 0; //this is to handle the special case where all numbers are negative bool allNegatives = true; int largest = int.MinValue; for (int i = 0; i < array.Length; i++) { largest = largest > array[i] ? largest : array[i]; curMax = curMax + array[i]; if (curMax > maxSoFar) { maxSoFar = curMax; maxEnd = i; maxStart = curMaxStart; allNegatives = false; } else if (curMax <= 0) { curMax = 0; curMaxStart = i + 1; } } if (allNegatives) { return largest; } return maxSoFar; }

### Largest Sum Sub-Sequence Integer Array

Problem: Given an array on n integers, find a contiguous sub-sequence / subarray with largest sum.
Example: For an array of following elements { -1, 2, -4, 1, 3, -2 }, the sub-sequence with largest sum is 1,3
Solution:

Subscribe to:
Post Comments (Atom)

Thanks!

ReplyDeletevery clean solution, Thanks!

ReplyDeleteI have a doubt..

ReplyDeleteshouldn't the largest be initialized to

-int.MinValue?

If all numbers in the array are negative, then largest will be int.MinValue according to the above program and it will return the largest as answer. But the correct value should be the maximum number present in the array

Shouldn't need the special logic for the all negative case if you initialize maxSoFar to int.MinValue. Since you reset curMax to 0 for any negative result, for an all negative case you'll examine each value independently, and end up with the largest negative in maxSoFar.

ReplyDelete