Algorithms Forever ...: Largest subsequence in terms of absolute sum
void largest_consecutive_absolute_
Simply keep track of max and min at the same time in the above O(N) solution.
Read full article from Algorithms Forever ...: Largest subsequence in terms of absolute sum
Given an array of N integers (both positive and negative), find the sub-sequence with largest absolute sum.
For ex: Let A = {1 2 -5 4 5 -1 2 -11} then largest absolute sum is 11 with sub-sequence {-11}.
For ex: Let A = {1 2 -5 4 5 -1 2 -11} then largest absolute sum is 11 with sub-sequence {-11}.
Solution :
A simpler variant was previously discussed [Largest consecutive sum], here the difference being absolute sum.
We use the same algorithm of O(N) here too first to get highest positive sum and then highest negative sum and find the one with higher absolute value as the answer.
Complexity :We use the same algorithm of O(N) here too first to get highest positive sum and then highest negative sum and find the one with higher absolute value as the answer.
- Time : O(N)
- Space : O(1)
*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;
void largest_consecutive_absolute_
int pos_start, pos_end, pos_max, neg_start, neg_end, neg_max;
int i;
largest_consecutive_sum(input, N, &pos_start, &pos_end, &pos_max);
for(i=0; i<N; i++){
largest_consecutive_sum(input, N, &neg_start, &neg_end, &neg_max);
if(pos_max > neg_max){
else {
}int i;
largest_consecutive_sum(input, N, &pos_start, &pos_end, &pos_max);
for(i=0; i<N; i++){
input[i] = -1*input[i];
}largest_consecutive_sum(input, N, &neg_start, &neg_end, &neg_max);
if(pos_max > neg_max){
*start = pos_start;
*end = pos_end;
*max = pos_max;
}*end = pos_end;
*max = pos_max;
else {
*start = neg_start;
*end = neg_end;
*max = neg_max;
}*end = neg_end;
*max = neg_max;
Simply keep track of max and min at the same time in the above O(N) solution.
Read full article from Algorithms Forever ...: Largest subsequence in terms of absolute sum
