HDU 1003 Max Sum

xiaoxiao2021-02-28  19

最大子序列和。

动态规划思想,算基础的DP了,先放代码,再讲解:

#include <iostream> #include <cstdio> using namespace std; const int maxn = 100010; int mx, be, en; int num[maxn]; int main() { int t, n, i, pt, x = 0; scanf("%d", &t); while(t--) { mx = -1001, pt = 1; scanf("%d", &n); for(i=1; i<=n; i++) { scanf("%d", &num[i]); } for(i=1; i<=n; i++) { if(num[i-1] >= 0) { num[i] += num[i-1]; } else { pt = i;//pt这个变量和运算没有关系,只是用来标记范围的 } if(num[i]>mx) { mx = num[i]; be = pt; en = i; } } printf("Case %d:\n", ++x); cout << mx << " " << be << " " << en << endl; if(t) cout << endl; } return 0; }

之前没了解DP,在找最大和时用了for循环嵌套,然后就超时了。。。

关键是这个:

num[i] += num[i-1];

因为要的是和最大,所以可以直接一个加一个,遇到负数要跳过,这样不管怎么加都是越来越大。

找出负数时,就意味着我们已经不会再用前面的标号了,这时候把pt更新,以便更新后面的和(如果比mx大的话)

转载请注明原文地址: https://www.6miu.com/read-2600123.html

最新回复(0)