Problem Description

Now I think you have got an AC in Ignatius.L's "Max Sum" problem. To be a brave ACMer, we always challenge ourselves to more difficult problems. Now you are faced with a more difficult problem.



Given a consecutive number sequence S1, S2, S3, S4 ... Sx, ... Sn (1 ≤ x ≤ n ≤ 1,000,000, -32768 ≤ Sx ≤ 32767). We define a function sum(i, j) = Si + ... + Sj (1 ≤ i ≤ j ≤ n).



Now given an integer m (m > 0), your task is to find m pairs of i and j which make sum(i1, j1) + sum(i2, j2) + sum(i3, j3) + ... + sum(im, jm) maximal (ix ≤ iy ≤ jx or ix ≤ jy ≤ jx is not allowed).





But I`m lazy, I don't want to write a special-judge module, so you don't have to output m pairs of i and j, just output the maximal summation of sum(ix, jx)(1 ≤ x ≤ m) instead. ^_^

 

Input

Each test case will begin with two integers m and n, followed by n integers S1, S2, S3 ... Sn.

Process to the end of file.

 

Output

Output the maximal summation described above in one line.

 

Sample Input

1 3 1 2 3

2 6 -1 4 -2 3 -2 3

 

Sample Output

6

8

Hint

Huge input, scanf and dynamic programming is recommended.

Author

JGShining（极光炫影）

题目大意：给你两个数M和N，之后是N个数，从这N个数找到M个子段，

求M个子段的最大和

思路：一開始不懂怎么找状态转移方程。

參考别人博客才明确。

.设dp[i][j] 为将前 j 个数字分成 i 段的最大和。num[j]为当前数字

那么转移方程为 dp[i][j] = max(dp[i][j-1]+num[j]，dp[i-1][k]+num[j]) (i-1<=k<=j-1)

也能够视为 dp[i][j] = max(dp[i][j-1]+num[j]，max(dp[i-1][i-1],dp[i-1][i],…,dp[i-1][j-1])
)

//注：max(dp[i-1][i-1],dp[i-1][i],…,dp[i-1][j-1]) 就是dp[i-1][j-1]

意思是：前 j 个数字分成 i 段的最大和有两个决策。

1、将当前第j个数字并入第i段，与第j-1个数字所在的一段并为一段的最大和。

2、将当前第j个数字作为第i段。而第k个数字所在的一段为第i-1段，区间(k+1,j-1)的数字

不再选则的最大和。

取这两个决策中最大值。

本题另一个难点在于将二维转为一位数组。

考虑到第i行的状态由第i-1行和第i行递推过来，

所以能够利用滚动数组将二维压缩为一维数组，过程有点不太理解。留到以后慢慢想。

參考博文：http://blog.csdn.net/acm_davidcn/article/details/5887401

#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;

int dp[1000010];

int maxn[1000010];

int num[1000010];

int main()

{

    int M,N;

    while(~scanf("%d%d",&M,&N))

    {

        dp[0] = maxn[0] = 0;

        for(int i = 1; i <= N; i++)

        {

            scanf("%d",&num[i]);

            dp[i] = maxn[i] = 0;

        }

        int MAXN;

        for(int i = 1; i <= M; i++)//分为i段

        {

            MAXN = -0xffffff0;

            for(int j = i; j <= N; j++)//第j个数字

            {

                dp[j] = max(dp[j-1]+num[j],maxn[j-1]+num[j]);

                maxn[j-1] = MAXN;

                MAXN = max(MAXN,dp[j]);

            }

        }

        printf("%d\n",MAXN);

    }

    return 0;

}