再次感谢题解区大佬的指点

规定\(pre[i]\)表示前缀\(i\)的前缀和,\(sum[i][j]\)表示区间\([i,j]\)之和

令\(f[i][j]\)表示前i个数选出j段的最大值,\(g[i][j]\)表示前i个数选出j段,且第一段一定选到第一个位置的最大值(这里都不强制选第\(i\)个数)

至于转移,枚举j,然后从前往后枚举\(i\),可以从\(f[i-1][j]\)转移过来,也可以另选一段.

这里记录一个前缀最大值\(ma=max(f[l][j-1]-pre[l])(l<i)\),转移时从\(ma+pre[i]\)转移

因为\(ma+pre[i]=max(f[l][j-1]-pre[l])+pre[i]=max(f[l][j-1]-pre[l]+pre[i])=max(f[l][j-1]+sum[l+1][i])(l<i)\)

预处理时,\(\forall i\ f[i][0]=0\)并且\(g[i][1]\)取最大前缀和

// luogu-judger-enable-o2

#include<algorithm>

#include<iostream>

#include<cstring>

#include<complex>

#include<cstdio>

#include<vector>

#include<cmath>

#include<ctime>

#include<queue>

#include<map>

#define LL long long

#define il inline

#define re register

using namespace std;

const LL mod=1000000007;

il LL rd()

{

    re LL x=0,w=1;re char ch;

    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}

    return x*w;

}

int a[100010],hd,tl,n,k;

int f[100010][60],g[100010][60],ans,mi;

int main()

{

  n=rd(),k=rd();

  for(int i=1;i<=n;i++) a[i]=rd()+a[i-1];

  memset(f,-0x3f3f3f,sizeof(f));

  memset(g,-0x3f3f3f,sizeof(g));

  mi=f[0][0];

  for(int i=0;i<=n;i++) f[i][0]=0;

  for(int j=1;j<=k;j++)

    {

      int ma=mi;

      for(int i=j;i<=n;i++)

        {

          f[i][j]=max(f[i-1][j],ma+a[i]);

          ma=max(ma,f[i][j-1]-a[i]);

        }

    }

  ans=f[n][k];

  for(int i=1;i<=n;i++) g[i][1]=max(g[i-1][1],a[i]);

  for(int j=2;j<=k;j++)

    {

      int ma=mi;

      for(int i=j;i<=n;i++)

        {

          g[i][j]=max(g[i-1][j],ma+a[i]);

          ma=max(ma,g[i][j-1]-a[i]);

        }

    }

  for(int i=k;i<=n;i++) ans=max(ans,g[i][k]+a[n]-a[i]);

  printf("%d\n",ans);

  return 0;

}