Solution:
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:
1. Time: O(N)
2. Space: O(1)
Code:
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++){
sum += input[i];
if(sum < 0){
sum = 0;
current = i+1;
}
if(sum > *max){
*max = sum;
*start = current;
*end = i;
}
}
}
void largest_consecutive_absolute_sum(int input[], int N, int *start, int *end, int *max){
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++){
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;
}
else {
*start = neg_start;
*end = neg_end;
*max = neg_max;
}
}
|
Posts
