Algorithms Forever ...: Largest Sum of Consecutive Numbers
For ex: Let A = {1 2 -5 4 5 -1 2 -11} then
Read full article from Algorithms Forever ...: Largest Sum of Consecutive Numbers
Given an array of N integers (both positive and negative), find the sub-sequence with largest sum.
For ex: Let A = {1 2 -5 4 5 -1 2 -11} then
largest sum is 10 (start index = 4, end index = 7)
{4 5 -1 2} (excluding end index)
{4 5 -1 2} (excluding end index)
void largest_consecutive_sum(int input[], int N, int *start, int *end, int *max){
*start = *end = *max = -1;
int current = -1;
int sum = 0;
for(int i=0; i<N; i++){
int current = -1;
int sum = 0;
for(int i=0; i<N; i++){
sum += input[i];
if(sum < 0){
if(sum > *max){
}if(sum < 0){
sum = 0;
current = i+1;
}current = i+1;
if(sum > *max){
*max = sum;
*start = current;
*end = i;
}*start = current;
*end = i;
}
http://n1b-algo.blogspot.com/2010/03/largest-sum-of-consecutive-numbers.html
The naive solution to this problem can be formulated and coded in O(N^3) time. Consider every possible pair of start and end index and calculate sum of the elements within those index and keep track of the max sum. The following code performs that
If we save the cumulative sum of elements in an array CSUM, then CSUM[i] indicates the sum of elements enclosed in indices (1,i), CSUM[j]-CSUM[i-1] would then indicate the sum of elements enclosed in indices (i,j). The following algorithm captures this intuition.
max = - Inf
imax = jmax = -1
for i = 1 to N
for j = i to N
// get sum of elements enclosed in index (i,j)
s = 0
for k = i to j
s += A[k]
if s > max
max = s
imax = i
jmax = j
Clearly the above algorithm is O(N^3). We can definitely improve the running time of the above algorithm. After observing carefully, we can see that an operation that is run several times (O(N^2) times) is computing the sum of elements between indices i,j. Can we do it quickly. Indeed we can. If we save the cumulative sum of elements in an array CSUM, then CSUM[i] indicates the sum of elements enclosed in indices (1,i), CSUM[j]-CSUM[i-1] would then indicate the sum of elements enclosed in indices (i,j). The following algorithm captures this intuition.
csum[0] = 0
for i = 1 to N
csum[i] = csum[i-1] + A[i]
max = - Inf
imax = jmax = -1
for i = 1 to N
for j = i to N
s = CSUM[j] - CSUM[i-1]
if s > max
max = s
imax = i
jmax = j
This is the best we can do with this approach. This problem can be done in O(N) time using a clever approach. Consider a sub-sequence with sum s > 0. Let the next element n is such that s + n < 0. Clearly this sub-sequence cannot be part of largest subsequence that contains s and n as removing s,n from that sub-sequence we get a larger sum. Easy to prove using contradiction. This idea is captured in the following O(N) algorithm max = -Inf
imax = jmax = -1
i_temp = -1
s_temp = 0
for i = 1 to N
s_temp += A[i]
if s_temp > max
// keep track of max so far
max = s_temp
imax = i_temp
jmax = i
if s_temp < 0
// abort this sub-sequence
s_temp = 0
i_temp = i + 1
Read full article from Algorithms Forever ...: Largest Sum of Consecutive Numbers
