Max Sum
http://acm.hdu.edu.cn/showproblem.php?pid=1003
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
这是一类典型的动态规划题目,一维数组。
将数组中的数字逐一相加。
如果发现当前的和小于0,则抛弃前面一段,将sum重置为0。记录下一个为准最大段起始位置。
如果和大于等于0,则加上这一段。
如果和大于最大值max,记录这个max值,并更新最大段其实和终止位置。
注:
max初值必须小于数组中数据的最小值。
此题输出格式,当有多个测试用例的时候,最后一个不允许出现多余空行,其它相邻两个用例间加入一个空行。
http://acm.hdu.edu.cn/showproblem.php?pid=1003
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
这是一类典型的动态规划题目,一维数组。
将数组中的数字逐一相加。
如果发现当前的和小于0,则抛弃前面一段,将sum重置为0。记录下一个为准最大段起始位置。
如果和大于等于0,则加上这一段。
如果和大于最大值max,记录这个max值,并更新最大段其实和终止位置。
注:
max初值必须小于数组中数据的最小值。
此题输出格式,当有多个测试用例的时候,最后一个不允许出现多余空行,其它相邻两个用例间加入一个空行。
#include <stdio.h> #include <stdlib.h> int main (int argc, char const* argv[]) { int i, c, t, n, sum, max, first, last, temp; int a[100000]; scanf("%d", &t); c = 1; while (c <= t) { scanf("%d", &n); for (i = 0; i < n; i++) { scanf("%d", &a[i]); } sum = 0; max = -1001; first = 0; last = 0; temp = 1; for (i = 0; i < n; i++) { sum += a[i]; if (sum > max) { max = sum; first = temp; last = i + 1; } if (sum < 0) { sum = 0; temp = i + 2; } } printf("Case %d:\n", c); printf("%d %d %d\n", max, first, last); if (c != t) printf("\n"); c++; } return 0; }
发表评论
-
fhloj1051 投票
2013-07-04 19:42 0投票 源文件: b(.bas/.c/.cpp/.pas) 输 ... -
fhloj1050 足球赛
2013-07-04 19:36 603足球赛 源文件: a(.bas/.c/.cpp/.pas) ... -
fhloj1092 五子棋
2013-07-04 12:01 726五子棋 源文件: gobang(.bas/.c/.cpp/ ... -
fhloj1091 拼单词
2013-07-04 11:53 748拼单词 源文件: words ... -
fhloj1090 21点游戏
2013-07-04 11:44 63621点游戏 源文件: poker(.bas/.c/.cpp ... -
fhloj1089 帮奶奶算帐
2013-07-04 11:17 596帮奶奶算账 源代码:bill.bas/pas 输入文件:bil ... -
hdu1019 gcd和lcm
2012-12-06 15:09 810Least Common Multiple http://a ... -
hdu1021 推理规律
2012-12-06 09:24 936Fibonacci Again http://acm.hdu ... -
hud1008 电梯 迭代模拟计算
2012-12-04 18:24 1040Elevator http://acm.hdu.edu.cn ... -
hdu1001 求和
2012-12-03 22:05 774Sum Problem http://acm.hdu.edu ... -
hdu1000 A+B
2012-12-03 18:37 858A + B Problem http://acm.hdu.e ... -
hdu2035 乘方取余
2012-12-02 18:02 1127人见人爱A^B http://acm.hdu.edu.cn/ ... -
hdu2034 差集
2012-12-02 17:43 856人见人爱A-B http://acm.hdu.edu.cn/ ... -
hdu2033 时间计算
2012-12-02 16:24 900人见人爱A+B http://acm.hdu.edu.cn/ ... -
hdu2081 字符串拼接
2012-12-01 14:35 860手机短号 http://acm.hdu.edu.cn/sho ... -
poj1163 树型结构动态规划和最大路径
2012-11-30 22:05 1190The Triangle http://poj.org/pr ... -
POJ1579递归函数定义
2012-11-30 21:58 852Function Run Fun http://poj.or ... -
POJ1050 最大子矩阵
2012-11-30 11:34 1214To the Maxhttp://poj.org/proble ...
相关推荐
例如,1003 DP 经典问题,最大连续子段和;1024 经典 DP,最大 M 子段和;1025 经典 DP,最长递增子序列(要用 NLogN 的方法过);1051 经典贪心,也可以用 DP;1058 经典问题,丑数,DP;1081 经典 DP 等等。 搜索...
题目名为“hdu 1257 最低拦截系统”,这里的“最低拦截系统”实际上是描述了一个问题场景,而具体的问题通过描述部分可以得知是要求找出给定数组中的最长递增子序列的长度。这里所谓的“最低拦截系统”可能是为了...
- 定义状态$sum[i]$表示以第$i$个元素结尾的最大连续子数组和。 - 状态转移方程:$sum[i] = \max(sum[i-1] + a[i], a[i])$。 - 最大值的计算可以通过维护一个变量`Max`来完成,遍历数组时不断更新`Max`的值即可。...
- 特殊情况下,数组中的所有元素均为负数时,最大连续子序列和为数组中的最大元素。 - 可以使用更简洁的代码实现,如示例代码所示。 #### 四、LargestRectangle (最大矩形面积) **问题描述:** 本题要求在一组高度...
本题属于动态规划的经典应用,要求找出一个数组中连续子序列的最大和。代码中定义了两个辅助数组`a`和`sum`,其中`sum[i]`表示以`a[i]`结尾的最大子序列和。通过比较`sum[i-1]`和0的大小,决定是否将当前元素加入...
- **1003**:DP经典问题,最大连续子段和,要求参赛者掌握一维DP的基本框架。 - **1024**:经典DP题目,最大M子段和,这是对1003题目的扩展,要求学生进一步理解DP的原理。 - **1025**:经典的DP题目,最长递增子...
这个问题寻找数组中的最大连续子序列和。状态方程可以表示为:`sum[i]=max(sum[i-1]+a[i], a[i])`,或者采用双指针方法进行遍历计算。 4. **Largest Rectangle**(题目链接:...
问题的核心在于从给定的一组数字中找出连续子数组,使得该子数组的元素之和最大。例如,在数组`[-2, 1, -3, 4, -1, 2, 1, -5, 4]`中,最大子数组为`[4, -1, 2, 1]`,其元素之和为6。 ### 二、基本版本:最大子段和 ...
5. **最大和问题**:在`字数组最大和.cpp`中,可能涉及到的是寻找数组中连续子数组的最大和,也就是 Kadane's Algorithm 的应用。这是一个经典的动态规划问题,通过遍历数组,记录当前子数组的最大和与全局最大和。 ...
2. **例题HDU3415:** 给定一个环状序列,求一个和最大的连续子序列,长度小于等于K。通过将问题转化为寻找最大的(s[i]-s[j]),其中i-j,进而转化为区间最值问题,使用单调队列可以有效地解决。 #### 四、单调队列...
它们可能涉及到数组、链表的操作,要求求解特定条件下的子序列、区间和、最大/最小值等问题。解决这些题目时,理解并灵活运用尺取法至关重要。 总之,尺取法是一种强大且灵活的算法技巧,它在处理涉及数组和链表的...
它将一个线性序列分割成多个不连续的段,每一个节点代表一个区间,并且通过递归的方式将这些区间进一步分割为更小的子区间,直到每个叶子节点代表序列中的单一元素。 #### 二、线段树的功能 线段树的主要功能包括:...
4. **动态规划**:动态规划是解决优化问题的重要方法,通过建立状态转移方程来求解最优解,如背包问题、最长公共子序列、斐波那契数列等。 5. **贪心算法**:在部分问题中,局部最优解能导出全局最优解,贪心策略就...