Why my code is giving error after i submit code-CodePudding

In CodeChef website problem SQUIDRULE it is giving me a runtime error after submitting but when I run the program it is giving me right answer and also run sucessfully.

#include <stdio.h>

int main(void) {
    int T, s, a[1000], b[100];
    scanf("%d", &T);

    while (T--) {
        scanf("%d", &s);

        for (int i = 1; i <= s; i  ) {
            scanf("%d", &a[i]);
        }

        for (int i = 1; i <= s; i  ) {
            int sum = 0, c;

            for (int j = 1; j <= s; j  ) {
                sum = sum   a[j];
            }

            c = sum - a[i];
            b[i] = c;
        }

        for (int i = 1; i <=s; i  ) {
            for (int j = i   1; j <=s; j  ) {
                if (b[i] > b[j]) {
                    int c;
                    c = b[i];
                    b[i] = a[j];
                    b[j] = c;
                }
            }
        }

        printf("%d\n",b[s]);
    }

    return 0;
}

CodePudding user response：

From my top comments ...

In your second set of nested for loops, which take O(n^2) time, you are sorting [using slow bubble sort instead of qsort?]. At the end, you only want to print b[s].

AFAICT, you do not need to sort at all. You're just looking for the max value of the array, so you can calculate that in O(n) time.

Further, sum is invariant across all iterations of i. So, you can move the j loop above the second i and only calculate it once. Once again, you can reduce running time from O(n^2) to O(n)

As WeatherVane pointed out, you need [at least] 10,000 entries in a.

Additionally, you can eliminate the separate for loop for calculating the sum by doing this in the scanf loop.

Here is a refactored version:

#include <stdio.h>

#define AMAX    (100000   10)
int s, a[AMAX];
int sum;

int
fast(void)
{

    int mx = sum - a[0];

    for (int i = 1; i < s; i  ) {
        int c = sum - a[i];
        if (c > mx)
            mx = c;
    }

    return mx;
}

int
main(void)
{

    int T;
    scanf("%d", &T);

    while (T--) {
        scanf("%d", &s);

        sum = 0;
        for (int i = 0; i < s; i  ) {
            scanf("%d", &a[i]);
            sum  = a[i];
        }

        int v2 = fast();
        printf("%d\n",v2);
    }

    return 0;
}