Maximum Sub-Array Sum
by Isai Damier, Android Engineer @ Google

/*********************************************************************
 * 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}
 *   
 * 
 **********************************************************************/ 
 package algorithm.programming.dynamic;

import java.util.Arrays;

public class MaxSubarray {

  public int[] subArraySum(int A[]) {
    int[] m = new int[A.length];
    int startingIndex = A.length - 1;
    int endingIndex = 0;

    //find endingIndex
    m[0] = A[0];
    for (int i = 1; i < A.length; i++) {
      m[i] = Math.max(A[i], m[i - 1] + A[i]);
      if (m[endingIndex] < m[i]) {
        endingIndex = i;
      }
    }

    //find startingIndex
    Arrays.fill(m, 0);
    m[A.length - 1] = A[A.length - 1];
    for (int i = A.length - 2; i >= 0; i--) {
      m[i] = Math.max(A[i], m[i + 1] + A[i]);
      if (m[startingIndex] < m[i]) {
        startingIndex = i;
      }
    }

    if (endingIndex <= startingIndex) {
      return null;//no array size less than 2 allowed
    }
    int[] result = Arrays.copyOfRange(A, startingIndex, endingIndex + 1);

    return result;
  }
}
package algorithm.programming.dynamic;

import org.junit.Test;
import static org.junit.Assert.*;

public class MaxSubarrayTest {

  /**
   * Test of subArraySum method, of class MaxSubarray.
   */
  @Test
  public void testSubArraySum() {
    System.out.println("subArraySum");
    int[] lastTwo = {-1, -2, -3, -4, -5, 6, 7};
    int[] expResult = {6, 7};

    MaxSubarray instance = new MaxSubarray();
    int[] result = instance.subArraySum(lastTwo);
    assertArrayEquals(expResult, result);

    int[] firstTwo = {8, 9, -1, -2, -3, -4, -5};
    expResult = new int[]{8, 9};
    result = instance.subArraySum(firstTwo);
    assertArrayEquals(expResult, result);

    int[] midTwo = {-1, -2, -3, 12, 23, -4, -5};
    expResult = new int[]{12, 23};
    result = instance.subArraySum(midTwo);
    assertArrayEquals(expResult, result);

    int[] midWithNegative = {-1, -2, -3, 12, -4, 23, 0, -4, -5};
    expResult = new int[]{12, -4, 23};
    result = instance.subArraySum(midWithNegative);
    assertArrayEquals(expResult, result);

    int[] flat = {0, 0, 0, 0, 0, 0, 0, 0, 0};
    expResult = null;
    result = instance.subArraySum(flat);
    assertArrayEquals(expResult, result);

    int[] negatives = {-1, -2, -3, -4, -5};
    expResult = null;
    result = instance.subArraySum(negatives);
    assertArrayEquals(expResult, result);

    int[] positives = {1, 2, 3, 4, 5, 6, 7};
    result = instance.subArraySum(positives);
    assertArrayEquals(positives, result);

    int[] flatBump = {0, 0, 0, 0, 0, 0, 1};
    expResult = null;
    result = instance.subArraySum(flatBump);
    assertArrayEquals(expResult, result);

    int[] flatMidBump = {0, 0, 0, 0, 1, 0, 0};
    expResult = null;
    result = instance.subArraySum(flatMidBump);
    assertArrayEquals(expResult, result);

    int[] negativeBump = {-1, -1, -1, -1, -1, -1, 1};
    expResult = null;
    result = instance.subArraySum(negativeBump);
    assertArrayEquals(expResult, result);

    int[] negativeMidBump = {-1, -1, -1, -1, 1, -1, -1, -1};
    expResult = null;
    result = instance.subArraySum(negativeMidBump);
    assertArrayEquals(expResult, result);
  }
}