Problem statement: CDBSTR06 Problem - CodeChef
Using a linear approach, where if the next element is positive or 0 after the sum has been negative - start the subarray.
Else add to the sum started for the subarray.
If sum is greater than the max found so far, update the ans.
/* Linear algo. Knowing max subarray in A[1...j], deciding the max subarray in A[1...j+1], which is either the max subarray of A[1..j] or a subarray of form A[i...j+1], where 1 <= i <= j+1 */
#include <stdio.h>
#include <stdlib.h>
struct tuple{
int start, end;
long long int sum;
};
int main(){
int i, j, N, t, *A, start, end;
long long int sum, max_sum_sofar;
scanf("%d", &t);
while(t--){
scanf("%d", &N);
A = (int*)malloc(N *sizeof(int));
for(i=0; i < N; i++)
scanf("%d", A+i);
struct tuple ans;
j=0;
start =0; end =0; sum = A[0]; max_sum_sofar = A[0];
ans.start = start; ans.end = end; ans.sum = max_sum_sofar;
while(j+1 != N){
if(A[j+1] > sum && A[j+1] > sum + A[j+1]){ //sum <0 and a_i >=0
start = j+1; end = j+1;
sum = A[j+1];
}
else if(A[j+1] + sum >= sum && A[j+1] <= sum + A[j+1]) //sum >=0 and a_i >=0
sum += A[j+1];
else if(A[j+1] + sum < sum ) // sum >=< 0 and a_i <0
sum += A[j+1];
if(sum > max_sum_sofar){
max_sum_sofar = sum; end = j+1;
ans.start = start; ans.end = end; ans.sum = max_sum_sofar;
}
else if(sum == max_sum_sofar){
end = j+1;
if(end - start > ans.end - ans.start){
ans.end = end; ans.start = start;
}
}
j++;
}
for(i= ans.start; i <= ans.end; i++){
printf("%d", A[i]);
if(i != ans.end)
printf(" ");
}
free(A);
}
return 0;
}
could you PLEASE show me which test case fails. I thought an additional space after the last element was the culprit, but no.