从左向右看，对于i位置选出j个不相交连续字段，那么对于i位置来说就有两个选择：
首先要知道的是我们所确定的区间里面的j个不相交的连续字段必须以i所在的字段结尾（因为如果不以i所在的字段结尾的话那在前面一定有结尾的下标，那本身就不应该是i这个区间了。）
dp[i][j] = dp[i-1][j]+a[i];//i拼到i-1所在的字段称为一体。
dp[i][j] = dp[k][j-1]+a[i];//i自成一个字段。那么前面到底以哪个下标结尾才能最大需要去遍历寻找。
所以最后的状态转移方程为：dp[i][j] = max(dp[i-1][j], dp[k][j-1])+a[i];
但是直接遍历k的话就得再开一个二维数组，空间会爆掉。所以在这里对于k进行一个滚动数组来保存取j个字段的最大数，所以需要从后向前遍历j否则会有影响。
初始化也需要注意： 
    memset(dp, 128, sizeof(dp));
    memset(d, 128, sizeof(d));
    d[0] = 0;
    for (int i=0;i<=m;i++) {
        dp[0][i] = 0;
    }
//从左向右看，对于i位置选出j个不相交连续字段，那么对于i位置来说就有两个选择：
//首先要知道的是我们所确定的区间里面的j个不相交的连续字段必须以i所在的字段结尾（因为如果不以i所在的字段结尾的话那在前面一定有结尾的下标，那本身就不应该是i这个区间了。）
//dp[i][j] = dp[i-1][j]+a[i];//i拼到i-1所在的字段称为一体。
//dp[i][j] = dp[k][j-1]+a[i];//i自成一个字段。那么前面到底以哪个下标结尾才能最大需要去遍历寻找。
//所以最后的状态转移方程为：dp[i][j] = max(dp[i-1][j], dp[k][j-1])+a[i];

#include <bits/stdc++.h>

using namespace std;
#define int long long
const int maxn = 1e6+10;;
int n, m;
int a[maxn];
int dp[maxn][22];
int d[22];

signed main() {
    cin>>n>>m;
    memset(dp, 128, sizeof(dp));
    memset(d, 128, sizeof(d));
    for (int i=1;i<=n;i++) {
        cin>>a[i];
    }
    d[0] = 0;
    for (int i=0;i<=m;i++) {
        dp[0][i] = 0;
    }
    for (int i=1;i<=n;i++) {
        for (int j=m;j>=1;j--) {
            dp[i][j] = dp[i-1][j];
            if (i>1)
                dp[i][j] = max(dp[i][j], d[j-1]);
            dp[i][j] = dp[i][j] + a[i];
            d[j] = max(dp[i][j], d[j]);
        }
    }
    int ans = LONG_LONG_MIN;
    for (int i=1;i<=n;i++) {
        ans = max(ans, dp[i][m]);
    }
    cout<<ans;
    return 0;
}