题意:
一组数列,分成两组,求怎么分使两组分别的连续最大和加起来最大,输出总和
要点:
最大连续和的一个简单变形,先从左往右求一次dp,将对应的当前最大值存储下来。然后从右往左dp一次,计算最大值即可。
POJ2479:
| 15350322 | Seasonal | 2479 | Accepted | 564K | 438MS | C++ | 645B | 2016-04-04 10:23:19 |
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define maxn 100001
#define minx -99999999
int a[maxn],dp[maxn];int main()
{int t,n,sum,temp;scanf("%d", &t);while (t--){scanf("%d", &n);temp = minx; sum = 0;//这是一种新dp做法,用temp存储当前最大值for (int i = 1; i <= n; i++){scanf("%d", &a[i]);sum += a[i];if (sum > temp)temp = sum; //如果加上当前值更大,更新tempdp[i] = temp; //dp存储第i个数前的最大连续和if (sum < 0) //如果sum加上当前值小于0就舍去sum = 0;}int max = minx;sum = 0; temp = minx;for (int i = n; i > 1; i--){sum += a[i];if (sum > temp)temp = sum;if (temp + dp[i - 1]>max)//这里temp就是当前的最大值,因为不用dp所以不用存储max = temp + dp[i - 1];//注意这里是i-1,所以前面输入必须从1开始,而且不能等于1if (sum < 0)sum = 0;}printf("%d\n", max);}return 0;
}
POJ2593:
两道题一模一样,只要稍微改下数组范围即可
| 15350439 | Seasonal | 2593 | Accepted | 948K | 172MS | C++ | 759B | 2016-04-04 10:56:57 |
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define maxn 100050
#define minx -99999999
int a[maxn],dp[maxn];int main()
{int n,sum,temp;while(~scanf("%d",&n),n){temp = minx; sum = 0;//这是一种新dp做法,用temp存储当前最大值for (int i = 1; i <= n; i++){scanf("%d", &a[i]);sum += a[i];if (sum > temp)temp = sum; //如果加上当前值更大,更新tempdp[i] = temp; //dp存储第i个数前的最大连续和if (sum < 0) //如果sum加上当前值小于0就舍去sum = 0;}int max = minx;sum = 0; temp = minx;for (int i = n; i > 1; i--){sum += a[i];if (sum > temp)temp = sum;if (temp + dp[i - 1]>max)//这里temp就是当前的最大值,因为不用dp所以不用存储max = temp + dp[i - 1];//注意这里是i-1,所以前面输入必须从1开始,而且不能等于1if (sum < 0)sum = 0;}printf("%d\n", max);}return 0;
}