hdu1003 Max Sum--DP
发布日期:2021-10-03 20:31:50
浏览次数:5
分类:技术文章
本文共 1532 字,大约阅读时间需要 5 分钟。
原题链接:
一:原题内容
Problem Description
Given a sequence a[1],a[2],a[3]......a[n], your job is to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7), the max sum in this sequence is 6 + (-1) + 5 + 4 = 14.
Input
The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line starts with a number N(1<=N<=100000), then N integers followed(all the integers are between -1000 and 1000).
Output
For each test case, you should output two lines. The first line is "Case #:", # means the number of the test case. The second line contains three integers, the Max Sum in the sequence, the start position of the sub-sequence, the end position of the sub-sequence. If there are more than one result, output the first one. Output a blank line between two cases.
Sample Input
25 6 -1 5 4 -77 0 6 -1 1 -6 7 -5
Sample Output
Case 1:14 1 4Case 2:7 1 6
二:分析理解
一个简单动态规划。。。。
三:AC代码
#include#include #include using namespace std;int a[100010];int main(){ int T; scanf("%d", &T); for (int i = 1; i <= T; i++) { scanf("%d", &a[0]); for (int j = 1; j <= a[0]; j++) scanf("%d", &a[j]); int left = 1; int right = 1; int cnt = a[1]; int flag = 1; int max = a[1]; for (int k = 2; k <= a[0]; k++) { if (cnt < 0) { flag = k; cnt = a[k]; } else cnt += a[k]; if (cnt > max) { left = flag; right = k; max = cnt; } } printf("Case %d:\n%d %d %d\n", i, max, left, right); if (i != T) printf("\n"); } return 0;}
转载地址:https://blog.csdn.net/LaoJiu_/article/details/50933499 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
关注你微信了!
[***.104.42.241]2024年04月16日 21时32分16秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
《千年金融史》书中的精髓:金融是一部间机器,塑造了现代文明。
2019-04-26
《共同基金常识》书中的精髓:如何用好指数基金,做好理财投资?
2019-04-26
《金融的本质》书中的精髓:金融危机是如何产生的?以及美联储是如何应对金融危机的?
2019-04-26
《周期》书中的精髓:如何利用周期,掌握世界的发展趋势,实现财富积累。
2019-04-26
《伟大的博弈》书中的精髓:华尔街是如何从一条小街,一步步发展为世界金融中心的。
2019-04-26
《逃不开的经济周期》书中的精髓:经济周期是推动创新变革和经济增长以及复兴的关键力量。
2019-04-26
《动物精神》书中的精髓:人类的非理性面影响经济决策,这些有可能是金融危机的根源。
2019-04-26
《巴菲特法则》书中的精髓:用好巴菲特企业前景投资法则,股票投资稳赚不赔。
2019-04-26
《战胜华尔街》书中的精髓:业余投资者如何根据行业特点选好股票,赚得比专业的投资者还要多?
2019-04-26
《股市稳赚》书中的精髓:用简单的神奇公式进行股票投资,获得稳定而持久的收益。
2019-04-26
作文提升~老师整理的优美比喻句太实用
2019-04-26
作文提升~老师整理的优美拟人句太实用
2019-04-26
作文提升~老师整理的优美排比句太实用
2019-04-26
作文提升~老师整理的夸张句,太实用了,赶快收藏
2019-04-26