I’ve just opened Introduction to Algorithms on Divide-and-Conquer chapter, and found interesting item – The maximum-subarray problem. In book you can find implementation with complexity O(NlogN) with good explanation, but in Exercises part there is good task:
Use the following ideas to develop a nonrecursive, linear-time algorithm for the maximum-subarray problem. Start at the left end of the array, and progress toward the right, keeping track of the maximum subarray seen so far. Knowing a maximum subarray of A[1..j] , extend the answer to find a maximum subarray ending at index j+1 by using the following observation: a maximum subarray of A[1..j+1] is either a maximum subarray of A[1..j] or a subarray A[i..j+1], for some 1<=i<=j+1. Determine a maximum subarray of the form A[i..j+1] in constant time based on knowing a maximum subarray ending at index j .
So, That is easy, because there are some ideas, you just need to stop and think a bit and all will be clear …
As described in the book you need to return 3 params
– max sum
– start index of sub array
– end index of sub array
OK, lets go …
Firstly create return structure.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
public class SubArrayResult { final long sum; final int startIndex; final int endIndex; private SubArrayResult(long sum, int startIndex, int endIndex) { this.sum = sum; this.startIndex = startIndex; this.endIndex = endIndex; } public long getSum() { return sum; } public int getStartIndex() { return startIndex; } public int getEndIndex() { return endIndex; } @Override public String toString() { return "SubArrayResult{" + "sum=" + sum + ", startIndex=" + startIndex + ", endIndex=" + endIndex + '}'; } } |
After that try to create algorithm.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
public SubArrayResult findMaximumSubArray(int[] A) { long sum = ; long result = ; int start = ; int end = ; for (int i = ; i < A.length; i++) { if (sum == && A[i] <= ) { start = i + 1; continue; } sum += A[i]; if (sum > result) { end = i; result = sum; } if (sum < ) { start = i + 1; sum = ; } } return new SubArrayResult(result, start, end); } |
OK, what algorithm is doing:
– firstly run throughout all array
1 |
for (int i = ; i < A.length; i++) |
– skipping negative values and move start index
1 2 3 4 |
if (sum == && A[i] <= ) { start = i + 1; continue; } |
– just add next value to current sum
1 |
sum += A[i]; |
– check if current sum > result value, if yes, assign sum to result and move end to current index
1 2 3 4 |
if (sum > result) { end = i; result = sum; } |
– and last one if sum < 0 assign 0 to sum and move start to next index
1 2 3 4 |
if (sum < ) { start = i + 1; sum = ; } |
So, that is all 🙂