`
richard_ma
  • 浏览: 16171 次
最近访客 更多访客>>
社区版块
存档分类
最新评论

HDU1003最大连续子序列和

阅读更多
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初值必须小于数组中数据的最小值。
此题输出格式,当有多个测试用例的时候,最后一个不允许出现多余空行,其它相邻两个用例间加入一个空行。

#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;
}
分享到:
评论

相关推荐

    ACM HDU题目分类

    例如,1003 DP 经典问题,最大连续子段和;1024 经典 DP,最大 M 子段和;1025 经典 DP,最长递增子序列(要用 NLogN 的方法过);1051 经典贪心,也可以用 DP;1058 经典问题,丑数,DP;1081 经典 DP 等等。 搜索...

    hdu 1257 最低拦截系统 lis

    题目名为“hdu 1257 最低拦截系统”,这里的“最低拦截系统”实际上是描述了一个问题场景,而具体的问题通过描述部分可以得知是要求找出给定数组中的最长递增子序列的长度。这里所谓的“最低拦截系统”可能是为了...

    hdu动态规划算法集锦

    - 定义状态$sum[i]$表示以第$i$个元素结尾的最大连续子数组和。 - 状态转移方程:$sum[i] = \max(sum[i-1] + a[i], a[i])$。 - 最大值的计算可以通过维护一个变量`Max`来完成,遍历数组时不断更新`Max`的值即可。...

    HDU 动态规划(46道题目

    - 特殊情况下,数组中的所有元素均为负数时,最大连续子序列和为数组中的最大元素。 - 可以使用更简洁的代码实现,如示例代码所示。 #### 四、LargestRectangle (最大矩形面积) **问题描述:** 本题要求在一组高度...

    ACM入门十题(杭电oj)

    本题属于动态规划的经典应用,要求找出一个数组中连续子序列的最大和。代码中定义了两个辅助数组`a`和`sum`,其中`sum[i]`表示以`a[i]`结尾的最大子序列和。通过比较`sum[i-1]`和0的大小,决定是否将当前元素加入...

    hdu题目分类

    - **1003**:DP经典问题,最大连续子段和,要求参赛者掌握一维DP的基本框架。 - **1024**:经典DP题目,最大M子段和,这是对1003题目的扩展,要求学生进一步理解DP的原理。 - **1025**:经典的DP题目,最长递增子...

    DP46题.doc

    这个问题寻找数组中的最大连续子序列和。状态方程可以表示为:`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 的应用。这是一个经典的动态规划问题,通过遍历数组,记录当前子数组的最大和与全局最大和。 ...

    DP的单调队列优化-Yuiffy.pdf

    2. **例题HDU3415:** 给定一个环状序列,求一个和最大的连续子序列,长度小于等于K。通过将问题转化为寻找最大的(s[i]-s[j]),其中i-j,进而转化为区间最值问题,使用单调队列可以有效地解决。 #### 四、单调队列...

    算法竞赛专题解析--尺取法1

    它们可能涉及到数组、链表的操作,要求求解特定条件下的子序列、区间和、最大/最小值等问题。解决这些题目时,理解并灵活运用尺取法至关重要。 总之,尺取法是一种强大且灵活的算法技巧,它在处理涉及数组和链表的...

    线段树完整版

    它将一个线性序列分割成多个不连续的段,每一个节点代表一个区间,并且通过递归的方式将这些区间进一步分割为更小的子区间,直到每个叶子节点代表序列中的单一元素。 #### 二、线段树的功能 线段树的主要功能包括:...

    ACM培训讲义

    4. **动态规划**:动态规划是解决优化问题的重要方法,通过建立状态转移方程来求解最优解,如背包问题、最长公共子序列、斐波那契数列等。 5. **贪心算法**:在部分问题中,局部最优解能导出全局最优解,贪心策略就...

Global site tag (gtag.js) - Google Analytics