最大多子段和问题

因为本人觉得2024年蓝桥杯的最后一题属于此类别，所以在此总结以下。且这个问题困惑我许久，终于于一个下午“顿悟”（勉勉强强理解半分）
部分思路借鉴于csdn；日月火山
题目描述：给定一个包含 K个整数的序列 {N1,N2,…,NK}。
连续子序列定义为 {Ni,Ni+1,…,Nj}
，其中 1≤i≤j≤K
最大子序列是指序列内各元素之和最大的连续子序列。

例如，给定序列 {−2,11,−4,13,−5,−2}，它的最大子序列为 {11,−4,13}，其各元素之和为 20。

现在你需要求出最大子序列的各元素之和。

这里的问题就是一段和，我本来以为这个题目可以用双指针去解决。

写题解的时候才发现不行。个人觉得是因为没有单调性，就像例子中给出来的子序列，我想维护这个连续序列和但是这个值不是单调的，比如和从11走到-4的时候，和会被更新，但是紧接着又增大了。这就破坏了双指针的单调性。（感觉·对双指针的理解不是很透彻 QAQ）

也就是说这个序列和的性质应该与每个元素所绑定，这个时候就要记录以下以每个元素结尾的最大字段和的位置。定义以此为结尾的集合数组，dp[i]指的是以a[i]结尾的最大字段和。思路很想最长上升子序列说思路。至于为什么这样定义可以解决上面双指针的问题呢。先贴个代码

#include<iostream>

using namespace std;

int main()
{
//····处理输入
  dp[i]=max(dp[i-1]+a[i],a[i]); 
}

在脑海中模拟以下这个过程，类似于双指针的过程，但是又不是那么像。dp[i-1]就是以a[i-1]为结束的最大字段和，如果加上之后比a[i]单独成组要大，那么就把这个值加上。我丢，这里我有觉得双指针可以做了。

//·····
     int i=0;
     int res=0,sum=-100000;
     while(i<n)
     {
         i++;
         if(res+a[i]>a[i])
         {
             res+=a[i];
         }else res=a[i];
    sum=max(sum,res);
     }

这里一直搞混了更新的过程，不是res在降低（遇到负值）的时候就更新res，而是在新的元素假如序列比单独的一个元素的和要小的时候才要更新元素。
然而，双指针没法解决多子段和的问题。
这里就要添加一个新的维度，类似分组背包。
原本只是一个组，就是一个子序列，现在是多组，就有多个子序列。所以f[i][j]就标识以第j元素结尾，i字段的的最大字段和。
代码如下：

#include<iotream>

using namespace std;

int main()
{
int ans=-10000;
   for(int i=1;i<=m;i++)
{
    for(int j=i;j<=n;j++)
   {
        f[i][j]=d[i][j-1]+a[i];  //接在前一个组的后面
        for(int k=j-1;k>=i-1;k--)
         {
         f[i][j]=max(f[i][j],f[i-1][k]+a[j]);
         }
   }
     if(i==m) ans=max(ans,f[i][j]);  //这里的内层循环每做一次都要更新一下答案，因为不晓得是以哪个作为元素的结尾。
  }
}

画表格以理解。这里我觉得最难得就是理解循环的执行过程，表格是一个很好的方法。