Given a sequence of n real numbers A(1) ... A(n), determine a contiguous subsequence A(i) ... A(j) of length atleast L for which the sum of elements in the subsequence is maximized.
For the following array, where L = 3.
A = {-5, -1, 2, -3, 0, -3, 3,}
The best possible sum of at least length 3 would be 0, where the subsequence is the last three elements (0, -3, 3)
Another Array with L = 2;
A = {0, 5, -3, -1, 2, -4, -1, 7, 8}
Output = 15;
Set sumL to the sum of the first L array elements.
Set runningSum = sumL.
Set maxSum = sumL
For k = L + 1 up to n, the length of the array:
Set sumL = sumL + A(k) - A(k - L)
Set runningSum = max(runningSum + A(k), sumL)
Set maxSum = max(maxSum, runningSum)
Output maxSum
Inputs:
int [] A = {0, 5, -3, -1, 2, -4, -1, 7, 8};
int L = 2;
int [] B = {-5, -1, 2, -3, 0, -3, 3,};
L = 3;
Output:
Max sum: 15
Indices: i=7 : j=8
Max sum: 0
Indices: i=4 : j=6
//Solution → O(n) time and space: sum all the elements in sum[], then sum[i] - sum[i - l] is the sum of the
ReplyDelete//last L elements. Since we are looking for the largest sum at least L elements we need
//sum[i] - sum[i - l] == max. So we add minSum[] keeping the smallest sum up tp the given idx. The
//saerched result then will be sum[i] - minSum[i - L]
a[] = 3 4 1 -2 6 -22 9 11 -3
sum[] 0 3 7 8 6 12 -10 -1 10 7
minSum 0 0 0 0 0 0 -10 -10 -10 -10
sum[i] - minSum[i - L] 0 0 5 3 9 -10 -1 10 17
public void printMaxSumInterval(int[] a, int L) {
if (a.length == 0)
return;
int[] sum = new int[a.length + 1];
int[] minSum = new int[a.length + 1];
int[] dp = new int[a.length];
dp[0] = Integer.MIN_VALUE;
for (int i = 1; i < sum.length; i++) {
sum[i] = sum[i - 1] + a[i - 1];
minSum[i] = Math.min(minSum[i - 1], sum[i]);
if (i >= L)
dp[i - 1] = sum[i] - minSum[i - L];
}
printMaxInterval(dp);
}
private void printMaxInterval(int[] dp, int L) {
int endIdx = 0;
int startIdx = 0;
int maxSum;
for (int i = 1; i < dp.length; i++)
if (dp[endIdx ] < dp[i])
endIdx = i;
startIdx = endIdx - L + 1;
maxSum = dp[endIdx];
for (int i = 0; i < L; i++)
maxSum -= dp[endIdx - i];
while (maxSum > 0)
maxSum -=dp[--startIdx];
print(startIdx, endIdx);
}