UVA OnlineJudge 507 - Jill Rides Again wrong answer

Question

I've been doing UVA OnlineJudge 507 - Jill Rides Again. I wrote the code and it works on every testcase from 'debug' page and form other forum. But when I submitted to the online judge, it became wrong answer. Here is my code

#include <stdio.h>
int main() {
    int stop[30000];
    int n, m, i, j, ans, sum, imax, imin, tmin, a = 1;

    scanf("%d", &n);
    while (n--) {
        // get all values
        scanf("%d", &m);
        stop[0] = 0;
        for (i = 1; i < m; i++) scanf("%d",&stop[i]);

        sum = ans = imax = imin = tmin = 0;
        for (i = 1; i < m; i++) {
            sum += stop[i];
            if (sum > ans || (sum == ans && (i - tmin) > (imax - imin))) {
                ans = sum;
                imax = i;
                imin = tmin;
            }

            if (sum <= 0) {
                tmin = i;
                sum = 0;
            }
        }

        if (ans > 0) {
            printf("The nicest part of route %d is between stops %d and %d\n", a++, imin + 1, imax + 1);
        } else {
            printf("Route %d has no nice parts\n", a++);
        }
    }
    return 0;
}

What is wrong with my code?

Answer 1

You're breaking the bicycle ride when sum of niceness is equal to 0 at the stop i, so you'll miss longer solution with the same sum, if the route with maximal possible niceness starts at the stop i.

I've changed condition if (sum <= 0) to if (sum < 0) and solution have passed all tests.

Answer 2

To answer your question, line if (sum <= 0) { should read if (sum < 0) {. The reason is that that way you don't reset the longest non-negative subsequence that ends in position i.

Your algorithm is esentially Kadane's Algorithm. I made a graphical explanation of why you should change the condition in line if (sum <= 0) { and of Kadane's Algorithm in general, which could help you understand the reason.