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

https://ac.nowcoder.com/acm/problem/235953

### 做法

``````#include<bits/stdc++.h>
#define endl "\n"
#define int long long
__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;
}
``````

07-17 23:59

1 收藏 评论