hdu1003 Max Sum--DP
发布日期:2021-10-03 20:31:50
浏览次数:6
分类:技术文章
本文共 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
不错!
[***.144.177.141]2024年04月08日 22时48分49秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
01 计算机视觉-opencv图像基本操作
2021-06-29
02 计算机视觉-opencv阈值与滤波处理
2021-06-29
03 计算机视觉-opencv图像形态学处理
2021-06-29
04计算机视觉-opencv图像梯度处理
2021-06-29
05计算机视觉-opencv边缘检测
2021-06-29
如何在junit中使用SpringFramework的Ioc容器
2021-06-29
一个案例教你理解Spring面向切面编程(Spring Aop)
2021-06-29
手把手教你整合SSM框架
2021-06-29
自己造个简单数据校验的注解@Value和@Mail
2021-06-29
Poj百练 4148:生理周期 (分类:枚举)
2021-06-29
java读写xlsx格式的MS Excel文件
2021-06-29
vue的一些基础知识点
2021-06-29
webpack错误记录(不定期更新)
2021-06-29
Poj百练 2692:假币问题 (分类:模拟)
2021-06-29
前后分但文件上传与多文件上传,前端实现
2021-06-29
SpringBoot自定义banner
2021-06-29
Poj百练 2746:约瑟夫问题 (分类:模拟)
2021-06-29
git知识点梳理
2021-06-29
git中tag标签的用法
2021-06-29
boost::bad_function_call用法的测试程序
2021-06-29