/*********************************************************************
* 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);
}
}