Given a sequence of n real numbers A(1) ... A(n), determine a contiguous subsequence A(i) ... A(j) for which the sum of elements in the subsequence is maximized.
Recurrence Equations:
For any i and j where (1 <= i < j <= n)
M(j) = Max sum over all windows ending at j.
M(j) = Max { M(j-1) + A[j], A[j] } ie either we extend the optimal window ending at j or start a fresh window with A[j].
Total time complexity: O(n) as there are n sub problems, each of size O(1).
Input Arrays:
int [] A = { -2, 11, -4, 13, -5, 2 };
int [] B = {-15, 29, -36, 3, -22, 11, 19, -5};
Output:
Max Sum: 20
Indices: i=1: j=3
Max Sum: 30
Indices: i=5: j=6
if (runningSum > 0) or if (runningSum > A[i])
ReplyDeletethanks good work
ReplyDeletei think this won't work if the array only has negative values.
ReplyDelete+1 for Vidudaya.
ReplyDeleteEvent it fails for smallest test case of negative numbers.
like if int C[] ={-2};
void maxContiguousSum(int A[], int len)
ReplyDelete{
unsigned start = 0 , finish = 0;
int prevSum = A[0];
int maxSum = A[0];
for( unsigned j = 1, i = 0; j < len; ++j )
{
int curSum = prevSum + A[j];
if( curSum > A[j] )
{
if( curSum > maxSum )//extend window
{
finish = j;
start = i;
maxSum = curSum;
}
prevSum = curSum;
}
else
{
if( A[j] > maxSum )// start new window
{
start = finish = j;
maxSum = A[j];
}
prevSum = A[j];
i = j;
}
}
cout << "Max Sum: " << maxSum << endl;
cout << "Indices: i=" << start << ": j=" << finish << endl;
}
int[] values = { -15, 29, -36, 3, -22, 11, 19, -5 };
ReplyDeleteint select,notSelect,total = values.LastOrDefault(),max = int.MinValue;
int j = values.Count();
for (int i = values.Count()-1; i >= 0; i--)
{
select = total + values[i];
notSelect = values[i];
total = Math.Max(select, notSelect);
if(total > max)
{
start = i;
if(total == notSelect) j = i;
end = j;
max = total;
}
}
Console.WriteLine("{0},{1},{2}", max,start, end);
Console.ReadLine();