Maximum Sub-Array Sum
by Isai Damier

#=======================================================================
# Author: Isai Damier
# Title: Maximum Sub-Array Sum
# Project: geekviewpoint
# Package: algorithms
#
# Statement:
#   Given an array of integers (possibly positive and negative),
#   find the sub-array whose sum is maximum. The sub-array must have
#   at least two elements.
#   Note: a sub-array is a continuous segment of an array.
#
# Time-complexity: O(n)
#
# Sample Input: {-1, 2, -3, 12, 23, -4, -5}
# Sample Output: {12, 23}
#
# Dynamic Programming Strategy:
#
#   Let's call the input array X. Then an easy solution to this problem
#   proceeds as follows:
#
#   0] scan X from left to right, tracking the sum of the maximal
#      sub-array that ends at index i.
#   1] scan X from right to left, tracking the sum of the maximal
#      sub-array that ends at index j.
#   2] find the maximum starting and ending indices (i.e. iMax and jMax)
#   3] then answer is the sub-array bounded by the iMax and jMax.
#
#   Implementing step 0 is actually easier than most people might at
#   first suspect. If we define array m so that m[i] is the sum of the
#   maximal sub-array that ends at index i, then for all i, m[i] is
#   simply the greater of X[i] and m[i - 1] + X[i]. We will illustrate
#   below.
#
#     i    sub-arrays ending at i       sum of maximal sub-array
#     0            {-1}                           m[0]=-1 : {-1}
#     1         {-1,2}; {2}                       m[1]=2  : {2}
#     2     {-1,2,-3}; {2,-3};{-3}                m[2]=-1 : {2,-3}
#     3   {-1,2,-3,12};{2,-3,12};{-3,12};{12}     m[3]=12 : {12}
#
#   At every step we pick the maximal sub-array from the bunch. If the
#   best sub-array ending at X[i-1] has a negative sum, i.e. m[i-1] < 0,
#   then there is no benefit to concatenating X[i-1] to X[i] since it
#   will pull X[i] down. On the other hand if m[i-1] is positive, the
#   best sub-array ending at i will be the one we picked at i-1 added
#   to X[i], as in the case where we picked {2,-3} over {-3} at i=2.
#
#   The final tally are
#
#   for step 0 is m={-1, 2, -1, 12, 35, 31, 26}
#   and for step 1 is m={33, 34, 32, 35, 23, -4, -5}.
#   Then for step 2, we use
#   the results from step 0 to get m[iMax]=35 so that iMax=4;
#   then we use the results from step 1 to get m[jMax]=35 so that jMax=3.
#   Hence the final answers {A[jMax],...,A[iMax]} = {A[3],A[4]} = {12,23}
#=======================================================================
 
 def subArraySum( A ):
  m = [0] * len( A )
  startingIndex = len( A ) - 1
  endingIndex = 0

  # find endingIndex
  m[0] = A[0]
  for  i in range( 1, len( A ) ):
    m[i] = max( A[i], m[i - 1] + A[i] )
    if ( m[endingIndex] < m[i] ):
      endingIndex = i

  # find startingIndex
  m = [0] * len( A )
  m[len( A ) - 1] = A[len( A ) - 1]
  for i in range( len( A ) - 2, -1, -1 ):
    m[i] = max( A[i], m[i + 1] + A[i] )
    if m[startingIndex] < m[i]:
      startingIndex = i

  if endingIndex <= startingIndex:
    return None # no array size less than 2 allowed

  result = A[startingIndex:endingIndex + 1]

  return result
import unittest
from dynamic_programming import MaxSubarray as algorithm

class Test( unittest.TestCase ):

  def testSubArraySum( self ):
    lastTwo = [-1, -2, -3, -4, -5, 6, 7]
    expResult = [6, 7]

    result = algorithm.subArraySum( lastTwo )
    self.assertEquals( expResult, result )

    firstTwo = [8, 9, -1, -2, -3, -4, -5]
    expResult = [8, 9]
    result = algorithm.subArraySum( firstTwo )
    self.assertEquals( expResult, result )

    midTwo = [-1, -2, -3, 12, 23, -4, -5]
    expResult = [12, 23]
    result = algorithm.subArraySum( midTwo )
    self.assertEquals( expResult, result )

    midWithNegative = [-1, -2, -3, 12, -4, 23, 0, -4, -5]
    expResult = [12, -4, 23]
    result = algorithm.subArraySum( midWithNegative )
    self.assertEquals( expResult, result )

    flat = [0, 0, 0, 0, 0, 0, 0, 0, 0]
    expResult = None
    result = algorithm.subArraySum( flat )
    self.assertEquals( expResult, result )

    negatives = [-1, -2, -3, -4, -5]
    expResult = None
    result = algorithm.subArraySum( negatives )
    self.assertEquals( expResult, result )

    positives = [1, 2, 3, 4, 5, 6, 7]
    result = algorithm.subArraySum( positives )
    self.assertEquals( positives, result )

    flatBump = [0, 0, 0, 0, 0, 0, 1]
    expResult = None
    result = algorithm.subArraySum( flatBump )
    self.assertEquals( expResult, result )

    flatMidBump = [0, 0, 0, 0, 1, 0, 0]
    expResult = None
    result = algorithm.subArraySum( flatMidBump )
    self.assertEquals( expResult, result )

    negativeBump = [-1, -1, -1, -1, -1, -1, 1]
    expResult = None
    result = algorithm.subArraySum( negativeBump )
    self.assertEquals( expResult, result )

    negativeMidBump = [-1, -1, -1, -1, 1, -1, -1, -1]
    expResult = None
    result = algorithm.subArraySum( negativeMidBump )
    self.assertEquals( expResult, result )