线性时间求解最大子序列和——HDU1003

水深无声 2022-05-16 10:27 122阅读 0赞

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

2  
5 6 -1 5 4 -7  
7 0 6 -1 1 -6 7 -5

Sample Output

Case 1:  
14 1 4  
  
Case 2:  
7 1 6

\#include <iostream> using namespace std; int main()\{ long cnt,n; long a\[100000\]; long temp\_sum, ts, te; long max\_sum, start, end; int i,j; j = 0; cin >> cnt; while(cnt--)\{ cin >> n; ++j; temp\_sum = max\_sum = -1024; for(i=0; i<n; ++i)\{ cin >> a\[i\]; \} for(i=0; i<n; ++i)\{ if(temp\_sum < 0)\{ if(a\[i\] > temp\_sum)\{ temp\_sum = a\[i\]; ts = te = i; if(temp\_sum > max\_sum)\{ max\_sum = temp\_sum; start = ts; end = te; \} \} \}else\{ temp\_sum += a\[i\]; te = i; if(temp\_sum > max\_sum)\{ max\_sum = temp\_sum; start = ts; end = te; \} \} \} cout << "Case " << j << ":" << endl; cout << max\_sum << " " << start+1 << " " << end+1 << endl; if(cnt) cout << endl; \} return 0; \}

发表评论取消回复

表情：

评论列表（有 0 条评论，122人围观）

还没有评论，来说两句吧...

相关阅读

相关 hdu1087（上升子序列的最大和）

[Problem - 1087 http://acm.hdu.edu.cn/showproblem.php?pid=1087][Problem - 1087 http_acm.

我会带着你远行/ 2022年10月21日 11:56/ 0 赞/ 142 阅读

相关 HDU 1231（最大连续子序列）

题意：如题。 include <stdio.h> int main() { int n, sum, ans,

落日映苍穹つ/ 2022年09月20日 11:28/ 0 赞/ 168 阅读

相关 hdu 题目1003 Max Sum （最大连续子序列和）

[http://acm.hdu.edu.cn/showproblem.php?pid=1003][http_acm.hdu.edu.cn_showproblem.php_pid

雨点打透心脏的1/2处/ 2022年09月17日 07:27/ 0 赞/ 110 阅读

相关最大子序列和

最大子序列和的4种算法给定整数A1,A2…An(可能有负数)求最大子序列和。（假设所有整数均为负数时，最大子序列和为0） Arg1 public int

一时失言乱红尘/ 2022年08月04日 04:18/ 0 赞/ 161 阅读

相关求解最大子序列算法及比较

include <iostream> include <stdlib.h> include <time.h> include "../StopW

谁践踏了优雅/ 2022年08月02日 06:22/ 0 赞/ 150 阅读

相关 hdu 1231 最大连续子序列

最大连续子序列 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Othe

拼搏现实的明天。/ 2022年05月31日 08:43/ 0 赞/ 149 阅读

相关最大子序列和

-------------------- 给定一个整数数组 `nums` ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。示例: 输入

淡淡的烟草味﹌/ 2022年05月22日 11:56/ 0 赞/ 157 阅读

相关 HDU1231“最大连续子序列”

原题链接：[http://acm.hdu.edu.cn/showproblem.php?pid=1231][http_acm.hdu.edu.cn_showproblem.ph

刺骨的言语ヽ痛彻心扉/ 2022年05月16日 21:12/ 0 赞/ 172 阅读

相关线性时间求解最大子序列和——HDU1003

Problem Description Given a sequence a\[1\],a\[2\],a\[3\]......a\[n\], your job is to c

水深无声/ 2022年05月16日 10:27/ 0 赞/ 123 阅读

相关 HDU 1231 最大连续子序列

原题目链接[HDU1231][] -------------------- 分类 HDU 动态规划最大连续子序列 --------------------

我不是女神ヾ/ 2022年04月16日 04:55/ 0 赞/ 191 阅读