1888. Circular Sequence

TAG 贪心算法

设数组sum记录序列和，要找一个最大的子序列，只需找出 asc=max { sum[b]-sum[a] } 0<=a<b<=n，因为我们只需要找出一个最大值，所以不需要O(n^2)，用pmin记录之前最小的sum[i],只需O(n)扫描一次即可。这样找到的子序列长度在1-n之间。

当然，还有一个问题要处理，序列接成一个圈。上面只求出一种情况，还有一种情况就是中间被舍弃，把首尾两段连接成子序列。我们只要仿照上面的方法，再求一个最小的子序列desc=min { sum[b]-sum[a] }，然后用sum[n]减去desc便能得到asc。但这里注意desc的长度为1-n，总长度减去desc后的长度为 0-(n-1)。我们要去掉0的情况，补上n的情况。

但具体的处理方法见代码。//ps: 程序的&sum 居然被替换成求和符号，汗。。我加了个空格

/* source code of submission 413424, Zhongshan University Online Judge System */
#include <stdio.h>
long long max(long long a, long long b)
{
    return a>b?  a: b;
}
long long sum[100003];
long long pmin,pmax,asc,desc;
long long ans1,ans2;
int n,t;
int main(int argc, char *argv[])
{
    scanf("%d", &t);
    while (  t-- )
    {
        scanf("%d",  &n);
        sum[0]=0;
        pmin=0;   
        pmax=0;
        desc=0;       //这里让desc小于等于0，
		              //序列递增时，最后找到的长度为0。但解已在asc，当然，sum[n]-desc也是解
        asc=-200000;  //这里asc允许小于0
        for (int i=1;  i<=n; ++i)
        {
            scanf("%lld", & sum[i]);
            sum[i]+=sum[i-1];
            if ( asc < sum[i]-pmin )
            {
                asc=sum[i]-pmin;
            }
            if ( desc > sum[i]-pmax )
            {
                desc=sum[i]-pmax;
            }
            if (  pmin>sum[i] )
            {
                pmin=sum[i];
            }
            if (  pmax<sum[i] )
            {
                pmax=sum[i];
            }
        }
        ans1=asc;
        if ( desc==sum[n] )//要不desc与sum[n]长度一样，不是解。
        {                  //要不如上面的右图，也不会是解。
            ans2=ans1-1;  //答案肯定在ans1了
        }
        else 
        {
            ans2=sum[n]-desc;
        }
        printf("%lld/n", max(ans1, ans2) );
    }
    return 0;
}