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! :slight_smile:

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 :man_shrugging:

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.

image
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.