Find the sub-array with the largest sum. [ALGORITHM PUZZLE Technical]

841.6K Views

You are given an array with integers (both positive and negative) in any random order.

Find the sub-array with the largest sum.

Share
Add Comment

  • 1 Answer(s)

    Assuming neither the array nor sub-array can be empty, there are two possibilities.

    1. Either all values in the array are negative, in which case the sub-array with the largest sum is the 1-element sub-array containing the maximum value, or
    2. There are non-negative values in the array and the sub-array is bounded by negative value(s) and/or the maximum/minimum indexes.

    The algorithm is to iterate through the array calculating the sum.  Whenever the sum drops below zero, reset the sum to zero and reset the low index.  Whenever the sum exceeds the maximum sum, record the new maximum and the sub-array indexes for the maximum.

    Given an array a of size s:

    msum = smallest negative integer
    mlow = -1
    mhigh = -1
    low = -1
    sum = 0
    for i = 0; i < s; i = i + 1 {
      if a[i] < 0 {
        if a[i] > msum {
          msum = a[i]
          mlow = mhigh = i
        }
        else {
          sum += a[i]
          if sum < 0 {
            sum = 0
            low = -1
          }
        }
      }
      else {
        if low == -1 {
          low = i
        }
        sum += a[i]
        if sum > msum {
          mlow = low
          msum = sum
          mhigh = i
        }
      }
    }
    // sub-array is a[mlow..mhigh] with a sum of msum
    

    dougbell Genius Answered on 24th October 2015.
    Add Comment
  • Your Answer

    By posting your answer, you agree to the privacy policy and terms of service.
  • More puzzles to try-