1 #include<iostream>
 2 #include<cstdio>
 3 #include<string.h>
 4 #define LL long long
 5 #define mem(a,b) memset(a,b,sizeof(a))
 6 using namespace std;
 7 LL dp[2][1000010];//dp[i][j]=k是i是分i段，j是前j个数，k是前j个数分i段的最大值 
 8 //dp[i][j]=max(dp[i][j-1]//不选第j个数,max（dp[i-1][k]/i-1<=k<j，dp[i][j-1])+第j个数//选第j个数） ,答案是dp[m%2][n];
 9 //可优化：即 1：dp[i-1][k]/i-1<=k<j，可用一个变量记录它
10 //            2： 只有dp[i][j-1]和dp[i-1][j-1]用得到，所以只需一维开2这么大就行 
11 int num[1000010];
12 LL up_max;
13 int main(){
14     int m,n;
15     int k;
16     while(~scanf("%d%d",&m,&n)){
17         mem(dp,0);
18         mem(num,0);
19         up_max=0;
20         for(int i=1;i<=n;i++){
21             scanf("%d",&k);
22             num[i]+=num[i-1]+k;
23         }
24         int t=0;
25         for(int i=1;i<=m;i++){
26             for(int j=i;j<=n;j++){
27                 if(i==j){
28                     up_max=dp[t][j]=num[j];//**！！！！*给dp赋初值，如果不写，则dp的第一个可能会是重j-1个数中选出i种，但是i==j只有从j个数中才可选出i种 
29                     //up_max是每一个重j-1分i段的最大和，所以也要赋初值 
30                 }else{
31                     up_max=max(up_max,dp[1-t][j-1])+num[j]-num[j-1];
32                     dp[t][j]=max(dp[t][j-1],up_max);
33                 }
34             }
35             t=1-t; //让数组一维滚动交换为（0，1）
36         }
37         t=1-t;//最后多减了一次，再减一下
38         cout<<dp[t][n]<<endl;
39     }
40     return 0; 
41 }