1 #include
     
       2 #include
      
        3 int dp[1000005],pre[1000005],a[1000005]; 4 int main() 5 { 6     int max1; 7     int i,j,n,m; 8     while (~scanf("%d%d",&m,&n)) 9     {10         for (i=1;i<=n;i++) scanf("%d",&a[i]);11         memset(dp,0,sizeof(dp));12         memset(pre,0,sizeof(pre));13         max1=-0x3f3f3f3f;14         for (i=1;i<=m;i++)15         {16             max1=-0x3f3f3f3f;17             for (j=i;j<=n;j++)18             {19                 if (dp[j-1]>pre[j-1]) dp[j]=dp[j-1]+a[j];20                                  else dp[j]=pre[j-1]+a[j];21                 pre[j-1]=max1;22                 if (dp[j]>max1) max1=dp[j];23             }24         }25         printf("%d\n",max1);26     }27     return 0;28 }