toj_2860.cpp

Tianjin University Online Judge 的80多道题目 .

/*2860.   Max Partial Sums Time Limit: 10.0 Seconds   Memory Limit: 65536K
Total Runs: 531   Accepted Runs: 147


Given a sequence of integers, namely (a1, a2, ... , an). The sum from ai to aj is called its partial sum. (1 ≤ i ≤ j ≤ n)

Now, you are asked to find m disjoint partial sums of a given sequence and make sure the total sum of these partial sums is largest.

Input
The input consists of several test cases. Each test case begins with a line containing two positive integers m and n. Then, n lines follow. Each line contains a single integer denoting the ith number of the sequence. (1 ≤ m ≤ 30, 1 ≤ n ≤ 1000000)

The input is terminated by the end of file.

Output
For each input test case, output the max total sum.

Sample input

3 5
2
3
4
-1
5

Sample output

14

Hint: The three partial sums are (2), (3, 4), (5) or (2, 3), (4), (5).

Source: TJU Team Selection Contest 1*/