HDU1024 Max Sum Plus Plus

解题思路：这题有一定难度，请参考http://www.cnblogs.com/kuangbin/archive/2011/08/04/2127085.html

见代码：

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 #define inf 0x3f3f3f3f
 5 const int maxn = 100005;
 6 int A[maxn], dp[maxn], max1[maxn];
 7 int main()
 8 {
 9     int n, m, MAX;
10     while(~scanf("%d %d", &m, &n))
11     {
12         for(int i = 1; i <= n; i++)
13         {
14             scanf("%d", &A[i]);
15             dp[i] = 0;
16             max1[i] = 0;
17         }
18         dp[0] = 0;
19         max1[0] = 0;
20         for(int i = 1; i <= m; i++)
21         {
22             MAX = -inf;
23             for(int j = i; j <= n; j++)
24             {
25                 dp[j] = max(dp[j-1]+A[j], max1[j-1]+A[j]);
26                 max1[j-1] = MAX;
27                 MAX = max(MAX, dp[j]);
28             }
29         }
30         printf("%d
", MAX);
31     }
32     return 0;
33 }

View Code