题解 | #最大m个子段和#

链接：https://ac.nowcoder.com/acm/problem/235953 来源：牛客网

给你一个数组 a ，包含 n 个整数，你需要在数组 a 中选出不相交的 m 个连续子段，每个子段的长度至少为 1 。

定义每一个子段的贡献为子段内数字的和，你需要求出这 mmm 个子段的贡献之和的最大值是多少。

做法

对于选择一个数，我们可以接到当前第j个字段的尾巴，或者另外开一个字段，那么状态就在f【i-1】【j】+a【i】，f【k】【j-1】中产生，其中k表示以第k个位置为前第一个子段，那么当前选择的数为第j个子段，那么直接去找k的话就是n^ 2的复杂度，所以我们要维护一个数组去优化复杂度，所以想到开一个d数组去维护，d【k】【j】的含义为第k个位置能凑成j个子段且和最大，那么我们可以省略掉一维，直接进行更新即可。

#include<bits/stdc++.h>
#define endl "\n"
#define int long long
/*inline __int128 read(){
    __int128 x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if(ch == '-')
            f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
inline void print(__int128 x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
        print(x / 10);
    putchar(x % 10 + '0');
}*/
//dont forget to check long long
//别写重变量名
//记得判越界
//别死磕
//处理字符串删掉关流
//用__int128时记得删掉关流
int f[1000010][22];
int d[22];
void slove()
{
    int n,m;
    std::cin>>n>>m;
    std::vector<int> a(n+1);
    for(int i=1;i<=n;i++) std::cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        for(int j=m;j>=1;j--)
        {
            f[i][j]=f[i-1][j];
            if(i>1) f[i][j]=std::max(f[i][j],d[j-1]);
            f[i][j]+=a[i];
            d[j]=std::max(d[j],f[i][j]);
        }
    }
    int ans=-1e9-10;
    for(int i=1;i<=n;i++)
    {
        ans=std::max(ans,f[i][m]);
    }
    std::cout<<ans<<endl;
}
signed main()
{
    int T=1; 
    //std::cin>>T;
    while(T--)    {
        slove();
    }

    return 0;
}