最大子段和-分治&&动态规划

   N个整数组成的序列a[1],a[2],a[3],…,a[n]，求该序列如a[i]+a[i+1]+…+a[j]的连续子段和的最大值。当所给的整数均为负数时和为0。

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

Input

第1行：整数序列的长度N（2 <= N <= 50000)
第2 - N + 1行：N个整数（-10^9 <= A[i] <= 10^9）

Output

输出最大子段和。

Input 示例

6
-2
11
-4
13
-5
-2

Output 示例

20

// 1.穷举50000显然超时，时间复杂度为O(n^2).

#include<iostream>
#include<cstdio>
using namespace std;
int a[50005];
int main()
{
   int i,j,n;
   while(~scanf("%d",&n))
   {
        for(i=0;i<n;i++)
            scanf("%d",a+i);
            __int64 max=0;
            for(i=0;i<n;i++)
            {
                __int64 sum=0;
                for(j=i;j<n;j++)
                {
                    sum+=a[j];
                    if(sum>max)
                        max=sum;
                }
            }
        printf("%I64d\n",max);
   }
    return 0;
}

/* 2.分治法  时间复杂度为O(nlogn).

求子区间及最大和，从结构上是非常适合分治法的，因为所有子区间[start, end]只可能有以下三种可能性:

在[1, n/2]这个区域内

在[n/2+1, n]这个区域内

起点位于[1,n/2],终点位于[n/2+1,n]内

以上三种情形的最大者，即为所求. 前两种情形符合子问题递归特性，所以递归可以求出. 对于第三种情形，则需要单独处理.

第三种情形必然包括了n/2和n/2+1两个位置，这样就可以利用第二种穷举的思路求出:

以n/2为终点，往左移动扩张，求出和最大的一个left_max

以n/2+1为起点，往右移动扩张，求出和最大的一个right_max

left_max+right_max是第三种情况可能的最大值

*/

#include<iostream>
#include<cstdio>
using namespace std;
int a[50005];
__int64 maxInterval(int *a,int l,int r)
{
    if(l==r)
        return a[l]>0?a[l]:0;
    int mid=(l+r)/2;
    __int64 leftmaxInterval=maxInterval(a,l,mid);
    __int64 rightmaxInterval=maxInterval(a,mid+1,r);
    int i;
    __int64 sum=0;
    __int64 left_max=0;
    for(i=mid;i>=l;i--)
    {
        sum+=a[i];
        if(sum>left_max)
            left_max=sum;
    }
    sum=0;
    __int64 right_max=0;
    for(i=mid+1;i<=r;i++)
    {
        sum+=a[i];
        if(sum>right_max)
            right_max=sum;
    }
    __int64 ans=left_max+right_max;
    if(leftmaxInterval>ans)
        ans=leftmaxInterval;
    if(rightmaxInterval>ans)
        ans=rightmaxInterval;
    return ans;
}
int main()
{
   int i,j,n;
   while(~scanf("%d",&n))
   {
        for(i=0;i<n;i++)
            scanf("%d",a+i);
        printf("%I64d\n",maxInterval(a,0,n-1));
   }
    return 0;
}

/* 3.动态规划法 计算时间复杂度为O(n),是最优的解

令b[j]表示以位置 j 为终点的所有子区间中和最大的一个

子问题:如j为终点的最大子区间包含了位置j-1,则以j-1为终点的最大子区间必然包括在其中

如果b[j-1] >0, 那么显然b[j] = b[j-1] + a[j]，用之前最大的一个加上a[j]即可，因为a[j]必须包含

如果b[j-1]<=0,那么b[j] = a[j] ,因为既然最大，前面的负数必然不能使你更大

*/

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int a[50005];
__int64 b[50006];
int main()
{
   // freopen("1.txt","r",stdin);
    __int64 max;
    int i,n,flag;
    while(~scanf("%d",&n))
    {
        flag=0;
        max=0;
        for(i=1; i<=n; i++)
        {
            scanf("%d",a+i);
            if(a[i]>0)
                flag=1;
        }
        memset(b,0,n+1);
        for(i=1; i<=n; ++i)
        {
            if(b[i-1]>0)
                b[i]=b[i-1]+a[i];
            else
                b[i]=a[i];
            if(b[i]>max)
                max=b[i];
        }
        if(flag)
            printf("%I64d\n",max);
        else
            puts("0");
    }
    return 0;
}