题目1527：首尾相连数组的最大子数组和-白红宇

题目1527：首尾相连数组的最大子数组和

阅读量：7296 次

发布时间：2019-06-30

本文共 3900 字，大约阅读时间需要 13 分钟。

本文为经典动态规划问题，数组的最大序列和和的延伸。第一次看见这个题，用了端点枚举的方法，复杂度为0(n^2)。超时严重。参考

这篇文章才明白O(n)的算法。

题目描述：给定一个由N个整数元素组成的数组arr，数组中有正数也有负数，这个数组不是一般的数组，其首尾是相连的。数组中一个或多个连续元素可以组成一个子数组，其中存在这样的子数组arr[i],…arr[n-1],arr[0],…,arr[j]，现在请你这个ACM_Lover用一个最高效的方法帮忙找出所有连续子数组和的最大值（如果数组中的元素全部为负数，则最大和为0，即一个也没有选）。输入：输入包含多个测试用例，每个测试用例共有两行，第一行是一个整数n（1=
     
      <=100000），表示数组的长度，第二行依次输入n个整数（整数绝对值不大于1000）。输出：对于每个测试用例，请输出子数组和的最大值。样例输入：61 -2 3 5 -1 256 -1 5 4 -7样例输出：1014 题目源地址：

该题需要证明：对于首尾相连的数组，划去其最大子数组和包含的数组元素，剩下的子数组必然是最小子数组和。可用反证法证明：

假设对于数组list[1...n]，剩下的子数组不是最小子数组和。

由于数组是首尾相连的，我们必然可以假设S1[1...i]为剩下的子数组，S2[i+1...n]为最大子数组。(S1和S2可代表子数组和的含义)。

case1:S1>=0，则S1+S2为最大子数组和，与条件冲突。

case2:S1<0，但不是最小子数组和序列。假设Sx为最小子数组和序列。

　　　　1）如果S2包含Sx，则S2必然不等于Sx。可将S2分为三部分。S2[i+1...n] = Sl[i+1...j] + Sx[j+1...k] + Sr[k+1...n].那么由于Sx < S1.则重新组合。Sr + S1 + Sl > Sl + Sx + Sr = S2.与条件矛盾。

　　　　2）如果S1包含Sx.但不等于Sx可以将S1分为三部分。S1[1..i] = Sl[1..j] + Sx[j+1...k] + Sr[k+1...i]。那么由于Sx < S1.所以Sl+Sr = S1-Sx > 0.重新组合，则Sr + S2 + Sl > S2..与条件矛盾。

　　　　3)如果Sx横跨S1和S2.那么可以将S1和S2分别分为两部分。Sl[1...j], Sm[j+1...i], Sn[i+1...k], Sr[k+1...n].且S1= Sl + Sm;S2 = Sn +Sr;Sx = Sm +Sn..由于Sx < S1,所以Sm < Sl.那么重新排列组合后Sr + Sl > Sr + Sm。与条件矛盾。

综上所述，结论得证。

所以我们只需讨论两者情况：　1）在首尾不相连的数组中，最大子数组和max.

　　　　　　　　　　　　　　2)在首尾相连的数组中，求最大子数组和，可以先求首尾不相连的数组中，最小子数组和min。然后Sum - min即为最大子数组和。

结果即为max和Sum - min中较大者。

AC代码：

#include 
     
       int main(){    int n;        int list[100010];         int max, min, sumMax, sumMin;        int total;    while(scanf("%d", &n) != EOF)    {        scanf("%d", &list[0]);        max = sumMax = list[0] > 0 ? list[0] : 0;        min = sumMin = list[0] < 0 ? list[0] : 0;        total = list[0];        for(int i = 1; i < n; i++)        {                        scanf("%d", &list[i]);            if(sumMax > 0)                sumMax += list[i];            else                sumMax = list[i];            if(sumMin < 0)                sumMin += list[i];            else                sumMin = list[i];            max = sumMax > max ? sumMax : max;            min = sumMin < min ? sumMin : min;            total += list[i];        }        int tmp = total - min;        printf("%d\n", max > tmp ? max : tmp);    }    return 0;}/**************************************************************    Problem: 1527    User: Qinger    Language: C++    Result: Accepted    Time:70 ms    Memory:1340 kb****************************************************************/

在九度论坛上，鬼M给出的是O（nlogn）的算法。。因为对线段树不太了解。所以先放在这里，有时间再看（希望如此）：

题目1：首尾相连数组的最大子数组和这个题目在之前的最大子段和的基础上扩展了一下，而且数据范围又比较大，不能通过枚举端点来实现题目要求的复杂度。对于这种循环的问题比较常见的一种方法是把这个数组扩大一倍。设原来的数组是a[],下标从1开始，为了方便设a[0]=0。sum[0]=0;sum [ i ]=a[1]+a[2]+a[3]+...+a [ i ]   (for each 1<=i<=2*n)然后我们求出以i为结尾的最大子段和。这个要从前面找一个j,使得sum [ i ] -sum[j]最大，而且i-j<=n,即要求最多只能有n个连续的数字也就是从区间[i-j,i-1]里面找一个sum的最小值，这个可以用线段树来实现。因此，这题可以用nlogn的复杂度解决了。当然此题还有其它的解法。有o(n)的，大家可以自行百度。 线段树：

#include
     
      #include
      
       #include
       
        #include
        #include
         
          #include
          
           using namespace std; const int MAX=110000*2; int sum[MAX];struct Q{ int id,v;}q[MAX];int front;int rear;void push(int id,int v){ rear++; q[rear].id=id; q[rear].v=v; while(rear-1>=front&&q[rear-1].v>q[rear].v) { rear--; q[rear]=q[rear+1]; }}int query(int id){ while(front<=rear&&q[front].id
           
            rear)return 0; return q[front].v;}int main(){ int n; int i; int CS=1; while(scanf("%d",&n)!=EOF) { sum[0]=0; for(i=1;i<=n;i++) { scanf("%d",&sum[i]); sum[i+n]=sum[i]; } for(i=1;i<=2*n;i++)sum[i]+=sum[i-1]; rear=-1; front=0; push(0,0); int ans=0; for(i=1;i<=2*n;i++) { int tmp=sum[i]-query(i-n+1); if(tmp>ans)ans=tmp; push(i,sum[i]); } printf("%d\n",ans); } return 0;} /************************************************************** Problem: 1527 User: 鬼M Language: C++ Result: Accepted Time:70 ms Memory:3600 kb****************************************************************/

转载于:https://www.cnblogs.com/xyqhello/p/3591286.html

你可能感兴趣的文章