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:
 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;
        }

4 comments:

  1. very clean solution, Thanks!

    ReplyDelete
  2. I have a doubt..
    shouldn'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

    ReplyDelete
  3. 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