N 個の整数の配列が与えられます。
配列の最大合計は、この配列の空でない連続する部分配列の要素の最大合計です。
たとえば、配列 [1, -2, 3, -2, 5] の最大合計は 6 です。これは、部分配列 [3, -2, 5] の合計が 6 であり、それ以上の部分配列合計を達成することが不可能であるためです。
これで、指定された配列から要素を 1 つしか削除できなくなりました。そうすることで達成できる結果の配列の最大可能最大合計はいくらですか?
私は自分のテストケースで自分のコードをテストしています。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;
}