# Maximum Sub-Array Sumby 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);
}
}
```