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

水深无声 2022-05-16 10:27 161阅读 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 条评论，161人围观）

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

相关阅读

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

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

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

相关最大子序列和

问题描述输入一组整数，求出这组数字子序列和中最大值。也就是只要求出最大子序列的和，不必求出最大的那个序列。例如：序列：\-2 11 -4 13 -5 -2，则最大子序列

曾经终败给现在/ 2022年09月30日 06:47/ 0 赞/ 157 阅读

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

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

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

相关 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 赞/ 153 阅读

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

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

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

相关最大子序列和

> 给定一个整数序列，a0, a1, a2,…, an（序列项可以为负数），求其中最大的子序列和，如果所有整数都是负数，那么最大子序列和为0；首先定义两个变量：max

本是古典何须时尚/ 2022年06月03日 02:00/ 0 赞/ 242 阅读

相关 hdu 1231 最大连续子序列

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

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

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

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

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

相关线性时间求解最大子序列和——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 赞/ 162 阅读

相关 HDU 1231 最大连续子序列

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

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