CareerCup

github.com/techpanja/interviewproblems/tree/master/src/arrays/maxsubarray

/**
* the task of finding the contiguous subarray which has the largest sum.
*
* Algo:----
*
* 1. Maintain two variables: maxSoFar and maxEndingAtCurrentPosition in Array.
* 2. Update maxEndingAtCurrentPosition if (maxEndingAtCurrentPosition + current[i]) > than 0.
* 3. Keep on updating maxSoFar whenever maxEndingAtCurrentPosition is greater than maxSoFar.
*
* en.wikipedia.org/wiki/Kadane%27s_Algorithm
* Date: 11/4/13
* Time: 3:23 PM
*/
public class FindMaxSubArray {

    private FindMaxSubArray() {

    }

    public static int findMaxOfSubArrayUsingMathMax(int[] inputArray) {
        int maxSoFar = 0;
        int maxEndingHere = 0;
        for (int i : inputArray) {
            maxEndingHere = Math.max(0, maxEndingHere + i);
            maxSoFar = Math.max(maxSoFar, maxEndingHere);
        }
        return maxSoFar;
    }

    public static String findMaxSubArrayUsingFor(int[] inputArray) {
        int maxSoFar = 0;
        int maxEndingHere = 0;
        int maxStartIndex = 0;
        int maxEndIndex = 0;
        for (int i = 0; i < inputArray.length; i++) {
            System.out.println("ending here " + maxEndingHere);
            System.out.println("so far " + maxSoFar);
            if (maxEndingHere + inputArray[i] > 0) {
                maxEndingHere = maxEndingHere + inputArray[i];
            } else {
                maxEndingHere = 0;
                maxStartIndex = i + 1;
            }
            if (maxEndingHere > maxSoFar) {
                maxSoFar = maxEndingHere;
                maxEndIndex = i;
            }
        }
        int[] maxArray = new int[0];
        if (maxStartIndex <= maxEndIndex) {
            maxArray = Arrays.copyOfRange(inputArray, maxStartIndex, maxEndIndex + 1);
        }
        return String.valueOf("\nInput-Array:" + Arrays.toString(inputArray)
                + "\nMax: " + maxSoFar
                + "\nSub-Array:" + Arrays.toString(maxArray));
    }
}

yeah, brute force would be the way to go unless there are some time/space requirements.

Finding a 1 million sequence subset within a 1 billion item array, this would not work very well, but author didn't really specify

public int maxSubArray(int[] A) {

if(A.length == 0) return 0;
if(A.length == 1) return A[0];
int[] sums = new int[A.length];
sums[0] = A[0];


for(int i=1; i < A.length; i++){
sums[i] = sums[i-1]>0?sums[i-1] + A[i]:A[i];
}

int max = A[0];
for(int i=0; i < sums.length; i++){
if(max < sums[i]) max = sums[i];
}

return max;

}

package ms.ArraysStrings;

public class MaxSubArraySum {

public int findMaxSum(int[] inputArray) {
int currentMax = 0, maxSum = 0;
int curStart = 0, curEnd = 0;
int start=0, end=0;
for (int i = 0; i < inputArray.length; i++) {
if (inputArray[i] > currentMax + inputArray[i]) {
currentMax = inputArray[i];
curStart = i;
curStart = i;
} else {
currentMax = currentMax + inputArray[i];
curEnd = i;
}
if (currentMax > maxSum) {
maxSum = currentMax;
start = curStart;
end = curEnd;
}
}
System.out.println("Start of Max "+start+ " "+"End of Max "+end);
return maxSum;
}



public static void main(String[] args) {
int[] inputArray = { -2, -3, 4, -1, -2, 1, 5, -3 };
MaxSubArraySum mSum = new MaxSubArraySum();
int output = mSum.findMaxSum(inputArray);
System.out.println("Maximum sub array sum " + output);
}

}