# Help needed in MaxSubArraySum

Problem statement: Contest Page | 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.

1 Like

Please format your code - the forum software has mangled it and it wonâ€™t compile!

I donâ€™t get itâ€¦by looking at the constraint for Ai in the question, shouldnâ€™t the answer be the sum of all elements in the array?

The example has negative A_i in it - thereâ€™s external contests for you

Yes, i thought that too, but then that wouldnâ€™t make sense, soâ€¦i just accepted there must negative A_i and got on with it

Thatâ€™s where I got confused XD

1 Like

Can you see the formatted code now? Thanks.

1 Like

Consider this test-case.

1
4
6 -1 9 -2

Correct output should be 9 but your code outputs 6 \ {-1} \ \ 9

But 6+(-1)+9 = 14 is greater than 9.

You cannot have negative numbers in your subarray

OH! So i understood the question wrong. Thank you so much.

1 Like

Okay so a followup question, what if the input is -9 -10?

Actually, it isnâ€™t mentioned in the problem but there wonâ€™t be test-case with no positive entries.