Solution:
brutal force solution is to enumerate all the subarrays and count the summary for each one of them. To realize with code, we have an outer loop i iterates through the start index of the subarray and inner loop j iterates through the end index of the subarray, then have a third loop k iterates through the elements in the subarray to count the sum. The time complexity is O(N^3).
Enumerate then sum has lots of redundancy, which can be saved. For example, when summarize {1, -2, 4, 8}, we can use the sum of {1, -2, 4} plus 8. Dynamic programing can help to reduce repeated calculation.
Assuming we have already known the max sum subarray for array arr[1...i - 1], notate the max sum All[i-1]. Now let's add element arr[i] into the picture to see if we got new max sum subarray. There are 3 possible scenarios:
- new max sum subarray contains a[i], the new max sum subarray is {<old-max-sum-subarray>, a[i]}, the All[i] = All[i-1] + a[i-1].
- new max sum subarray is a[i] itself, the new max sum subarray is {a[i]}, the All[i] = a[i].
- old max sum subarray remains unchanged, {<old-max-sum-subarray>}, the All[i] = All[i-1].
To formalize: All[i] = math.max(All[i - 1] + a[i], a[i], All[i - 1]).
public class maxSubArray {
public static void main(String...args) {
int arr[] = new int[] {1, -2, 4, 8, -4, 7};
System.out.println(maxSubArray(arr));
}
//time: O(N), space: O(1)
public static int maxSubArray(int[] arr) {
if(arr == null || arr.length < 1) {
System.out.println("arry is empty");
return -1;
}
int nAll = arr[0];
int nEnd = arr[0];
for(int i = 1; i < arr.length; i++) {
nEnd = Math.max(nEnd + arr[i], arr[i]); //no 3 param version in Math.max
nAll = Math.max(nEnd, nAll);
}
return nAll;
}
}
In order to find the elements of the max sum subarray, we need a new observation. From formula End[i] = Math.max(End[i - 1] + arr[i], arr[i]), we can find that: whenever End[i-1] < 0, End[i] = arr[i]. If any arr[i-1] makes End[i-1] < 0, the index i - 1 is a potential starting index for the max sum subarray.
public class maxSubArray {
private int start;
private int end;
public static void main(String...args) {
int arr[] = new int[] {1, -2, 4, 8, -4, 7};
maxSubArray msa = new maxSubArray();
System.out.println(msa.maxSubArray(arr));
System.out.println(msa.start + "," + msa.end);
}
//time: O(N), space: O(1)
public int maxSubArray(int[] arr) {
int maxSum = Integer.MIN_VALUE;
int nSum = 0;
int nStart = 0;
for(int i = 0; i < arr.length; i++) {
if(nSum < 0) {
nStart = i;
nSum = arr[i];
} else {
nSum += arr[i];
}
if(nSum > maxSum) {
maxSum = nSum;
start = nStart;
end = i;
}
}
return maxSum;
}
} 