51nod 1050 循环数组最大子段和 dp

比眉伴天荒 2022-08-20 12:28 28阅读 0赞

N个整数组成的循环序列a\[1\],a\[2\],a\[3\],…,a\[n\]，求该序列如a\[i\]+a\[i+1\]+…+a\[j\]的连续的子段和的最大值（循环序列是指n个数围成一个圈，因此需要考虑a\[n-1\],a\[n\],a\[1\],a\[2\]这样的序列）。当所给的整数均为负数时和为0。

例如：-2,11,-4,13,-5,-2，和最大的子段为：11,-4,13。和为20。

当要求不循环的时候问题相当简单，就是一个简单的dp，dp\[i\]表示的是前i个元素的最大连续子段和。dp\[i\] =max(dp\[i-1\]+a\[i\] , a\[i\]).

现在问题换成数组是可以循环的了，那么问题怎么解决呢。

我们可以分为两种情况，一种是最大值没有过界，那么就是上面的简单问题，另一种是过界了，这时候我们可以转换一下思路，要求过界的最大连续子段和我们可以求不过界的最小连续子段和，这样剩下的数字和不但是最大的并且是过界连续的。

//循环数组最大连续子序列
    #include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    
    int const maxn = 50005;
    long long a[maxn];
    
    
    long long  MAX(int n)
    {
        long long dp[maxn];
        dp[0] = 0 ;
        long long ans = 0 ;
        for(int i = 1 ; i <= n ; i++)
        {
            if(dp[i-1]>0)dp[i]=dp[i-1]+a[i];
            else dp[i]=a[i];
            if(dp[i]>ans)ans=dp[i];
        }
        return ans ;
    }
    
    long long MIN(int n)
    {
        long long dp[maxn];
        dp[0] = 0 ;
        long long ans = 0 ;
        for(int i = 1 ; i <= n ; i++)
        {
            if(dp[i-1]<0)dp[i]=dp[i-1]+a[i];
            else dp[i]=a[i];
            if(dp[i]<ans)ans=dp[i];
        }
        return ans ;
    }
    
    int main()
    {
        int n;
        while(scanf("%d",&n)!=EOF)
        {
            long long sum = 0 ;
            for(int i = 1 ; i <= n ; i++)
            {
                scanf("%I64d",&a[i]);
                sum+=a[i];
            }
            long long ans = max(MAX(n),sum-MIN(n));
            printf("%I64d\n",ans);
        }
        return 0;
    }
    
    
    
    
    
    //数组最大连续子序列
    //#include <iostream>
    //#include <cstdio>
    //#include <cmath>
    //#include <algorithm>
    //#include <cstring>
    //using namespace std;
    //
    //int const maxn = 50005;
    //long long a[maxn];
    //long long dp[maxn];
    //
    //int main()
    //{
    //    int n;
    //    while(scanf("%d",&n)!=EOF)
    //    {
    //        for(int i = 1 ; i <= n ; i++)
    //        {
    //            scanf("%I64d",&a[i]);
    //        }
    //        dp[0]=0;
    //        long long ans = 0 ;
    //        for(int i = 1 ; i <= n ; i++)
    //        {
    //            if(dp[i-1]>0)dp[i]=dp[i-1]+a[i];
    //            else dp[i]=a[i];
    //            if(dp[i]>ans)ans=dp[i];
    //        }
    //        printf("%I64d\n",ans);
    //    }
    //    return 0;
    //}