最大子段和

分治递归：

因为他要求的的是最大连续子序列和最大，所以，我们可以这样看：
找到一个点i 然后让把整个分成两段，一段是左段，一段是右端，然后再去找左段里的最大，和右端里的zuid
图片说明
还有一种：在左边找一段，或者在右边找一段最大的，构成整个最大。

ll solve(ll l,ll r){
    if(l==r) return a[l];
    ll mid=(l+r)/2;
    ll ans1=solve(l,mid);
    ll ans2=solve(mid+1,r);
    ll l1=0,r1=0;
    ll sum=0;
    for(int i=mid;i>=l;i--){
        sum+=a[i];
        l1=max(l1,sum);
    }
    sum=0;
    for(int i=mid+1;i<=r;i++){
        sum+=a[i];
        r1=max(r1,sum);
    }
    return max(l1+r1,max(ans1,ans2));
}

动态规划

动态规划就直接考虑状态转移方程就行了：

dp[i]=max(dp[i-1]+a[i],a[i]);

就是判断前一个连续最大的和加上这个数与这个数本身取最大。也就是最优。

n=read;
    for(int i=1;i<=n;i++)
        sf("%lld",&a[i]);
    dp[0]=-inf;
    for(int i=1;i<=n;i++){
        dp[i]=max(dp[i-1]+a[i],a[i]);        
    } 
    sum=-inf;
    for(int i=1;i<=n;i++)
    {
        sum=max(sum,dp[i]);
    }
    cout<<sum<<endl;

做这类题注意他的初始化要求有的是最小是为零，有的会让你出现负数也就是类似下面这句话

最大/小连续子序列积

我们要求的最大/小连续子序列积的话，首先这样考虑，第i个数是乘还是不乘上去，还有如果原本是正数，乘上一个负数他肯定没有原本不乘上去的结果大，所以我们在求最大也要保存下来最小，求最小也要保留下来最大，就是避免出现负数，导致答案没有达到最优。所以我们就会得到如下状态转移方程

ll temp=maxx;
maxx=max(a[i],max(maxx*a[i],minn*a[i]));
minn=min(a[i],min(minn*a[i],temp*a[i]));

当然我们也要在过程用记录过程中的最大最小这就不会遗漏结果。

ll temp=maxx;
maxx=max(a[i],max(maxx*a[i],minn*a[i]));
minn=min(a[i],min(minn*a[i],temp*a[i]));
ans1=max(ans1,maxx);
ans1=min(ans2,minn);

K个最大连续子序列和

首先我们可以知道，开一维数组是解决不了问题的，一维你不知道当前述归属于第几个数。
所以我们开二维数组，直接说最优的解法。

for(int i=1,k=1;i<=m;i++,k=!k)
     {
         maxx=-inf;
         for(int j=i;j<=n-m+i;j++){
             maxx=max(maxx,dp[!k][j-1]);
            dp[k][j]=max(maxx,dp[k][j-1])+a[j];
         }
     }
    ans=-inf; 
    for(int i=m;i<=n;i++){
        ans=max(ans,dp[m&1][i]);
    }
    cout<<ans<<endl;