c - 子数组中的最大和

Question

You're given an array of N integer numbers.
The maximal sum of the array is the maximal sum of the elements of a nonempty consecutive subarray of this array.
For example, the maximal sum of the array [1, -2, 3, -2, 5] is 6 because the sum of the subarray [3, -2, 5] is 6 and it is impossible to achieve greater subarray sum.
Now you're allowed to remove no more than one element from the given array. What is the maximal possible maximal sum of the resulting array you can achieve by doing so?

我正在用我自己的测试用例测试我的代码。我在 dev-c++ 上得到了正确的输出。但是当我在线测试我的代码时，我得到了错误的答案。我无法找出问题所在。

#include <stdio.h>
#include <limits.h>
#include <stdlib.h>
struct result{
    long long int start;
    long long int end;
    long long int sum;
}res;
long long int find_max(long long int a[],long long int n)
{
    long long int max=LLONG_MIN;
    long long int i;
    for(i=0;i<n;++i)
    {
        if(a[i]>max)
            max=a[i];
    }
    return max;
}
long long int max_sub(long long int a[],long long int n)
{
    long long int i;
    long long int min,sum1=0;
    struct result max,max_curr,*maxsub;
    maxsub=calloc(sizeof(res),n);
    max.sum=LLONG_MIN;
    max_curr=max;
    for(i=0;i<n;++i)
    {
        if(max_curr.sum<0)
        {
            max_curr.sum=a[i];
            max_curr.start=i;
            max_curr.end=i;
        }
        else
        {
            max_curr.sum+=a[i];
            max_curr.end=i;
        }
        if(max_curr.sum>max.sum)
        {
            max=max_curr;
        }
        maxsub[i]=max;
    }
    min=0;
    for(i=maxsub[n-1].start;i<=maxsub[n-1].end;++i)
    {
        if(a[i]<0)
        {
            if(min==0 || a[i]<min)
                min=a[i];
        }
    }
    sum1=maxsub[n-1].sum-min;
    return sum1;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        long long int n,i;
        scanf("%lld",&n);
        long long int a[n];
        for(i=0;i<n;++i)
            scanf("%lld",&a[i]);
        long long int sum=0;
        sum=find_max(a,n);
        if(sum<=0)
        {
            printf("%lld\n",sum);
        }
        else
        {
            sum=max_sub(a,n);
            printf("%lld\n",sum);
        }

    }
    return 0;
}

Answer 1

请关闭此线程。 OP 正试图通过在此处发布问题来在正在进行的在线竞赛中作弊。