当前位置: 代码迷 >> 综合 >> POJ2479POJ2593 Maximum sumMax Sequence(最大连续和)
  详细解决方案

POJ2479POJ2593 Maximum sumMax Sequence(最大连续和)

热度:21   发布时间:2024-01-16 13:47:43.0

题意:

一组数列,分成两组,求怎么分使两组分别的连续最大和加起来最大,输出总和

要点:

最大连续和的一个简单变形,先从左往右求一次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;
}



  相关解决方案