B

题意:给你一段序列,如果存在一段子序列之和大于序列总和,则输出NO,不存在则输出YES。

思路:因为是子序列所以不能等于序列,所以只要求1到n-1和2到n里的最大子序列与序列总和做比较。

#include<bits/stdc++.h>
#define N 1e5+10
using namespace std;
int main(){
        long long int t,n,a[int(N)],i,j,sum,k,maxx;
        while(~scanf("%lld",&t)){
                while(t--){
                        scanf("%lld",&n);
                        for(i=k=0;i<n;i++){
                                scanf("%lld",&a[i]);
                                k+=a[i];
                        }
                        for(i=0,sum=0,maxx=-1;i<n-1;i++){
                                sum+=a[i];
                                if(a[i]>sum) sum=a[i];
                                maxx=max(sum,maxx);
                        }
                        for(i=1,sum=0;i<n;i++){
                                sum+=a[i];
                                if(a[i]>sum) sum=a[i];
                                maxx=max(sum,maxx);
                        }
                        if(maxx>=k)
                                printf("NO
");
                        else    printf("YES
");
                }
        }
}
View Code
原文地址:https://www.cnblogs.com/DreamingBetter/p/12202301.html