1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define maxn 1000010 5 #define ll int 6 using namespace std; 7 const int inf=1<<29; 8  9 ll dp[maxn],pre[maxn];10 int a[maxn];11 int n,m;12 ll max2;13 14 ll max1(ll a,ll b)15 {16     if(a>b) return a;17     return b;18 }19 20 int main()21 {22     while(scanf("%d%d",&m,&n)!=EOF)23     {24         for(int i=1; i<=n; i++)25         {26             scanf("%d",&a[i]);27         }28         memset(dp,0,sizeof(dp));29         memset(pre,0,sizeof(pre));30         for(int i=1; i<=m; i++)31         {32             max2=-inf;33             for(int j=i; j<=n; j++)34             {35                 dp[j]=max(dp[j-1]+a[j],pre[j-1]+a[j]);36                 pre[j-1]=max2;37                 max2=max(max2,dp[j]);38             }39         }40         printf("%d\n",max2);41     }42     return 0;43 }