HDU 1003 maxsum

#include<iostream>
#include<vector>
using namespace std;

typedef struct {
    int maxsum;
    int first;
    int end;
}resultArryType;

void OutResult(vector<int> vec, int num)
{
    resultArryType resultArry;
    int max = 0;
    int numCount = 0;
    int maxsum = 0, sumtemp = 0;
    resultArry.maxsum = -1001;
    resultArry.end = 0;
    resultArry.first = 0;
    numCount = vec.size();
    for (int i = 0; i < numCount; i++){
        sumtemp = 0;
        for (int j = i; j < numCount; j++){
            sumtemp += vec[j];

            if (sumtemp > resultArry.maxsum){
                resultArry.maxsum = sumtemp;
                resultArry.first = i + 1;;
                resultArry.end = j + 1;
            }

            if (resultArry.maxsum >sumtemp && sumtemp < 0)
                break;
        }
    }
    cout << "Case " << num << ":" << endl;
    cout << resultArry.maxsum << " " << resultArry.first << " " << resultArry.end << endl;
}

int main()
{
    int num, temp;
    int first;
    vector<int> vec;

    cin >> num;
    for (int i = 0; i < num; i++){
        first = 0;
        cin >> first;
        vec.clear();
        for (int j = 0; j < first; j++){
            cin >> temp;
            vec.push_back(temp);
        }
        OutResult(vec, i+1);
        if (i < num - 1)
            cout << endl;
    }
}

  

时间: 06-27

HDU 1003 maxsum的相关文章

【ToReadList】六种姿势拿下连续子序列最大和问题,附伪代码(以HDU 1003 1231为例)(转载)

问题描述:       连续子序列最大和,其实就是求一个序列中连续的子序列中元素和最大的那个. 比如例如给定序列: { -2, 11, -4, 13, -5, -2 } 其最大连续子序列为{ 11, -4, 13 },最大和为20. =============================================================== 问题分析: 1.首先最朴素的方法是暴力 O(n^3) 直接两个for循环枚举子序列的首尾,然后再来个循环计算序列的和,每次更新和的最大值.

sum max(hdu 1003)

观察可以发现,0,1,2,--,n结尾的分组中, maxsum a[0] = a[0] maxsum a[1] = max( a[0] + a[1] ,a[1])  = max( maxsum a[0] + a[1] ,a[1]) maxsum a[2] = max( max ( a[0] + a[1] + a[2],a[1] + a[2] ),a[2]) = max(  max( a[0] + a[1] ,a[1]) + a[2] , a[2]) = max(  maxsum a[1] + a

[ACM] hdu 1003 Max Sum(最大子段和模型)

Max Sum Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 135262    Accepted Submission(s): 31311 Problem Description Given a sequence a[1],a[2],a[3]......a[n], your job is to calculate the max s

HDU 1003 Max Sum (动规)

Max Sum Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 141547    Accepted Submission(s): 32929 Problem Description Given a sequence a[1],a[2],a[3]......a[n], your job is to calculate the max s

HDU 1003 &amp;&amp; HDU 1081(最大子列和,最大子矩阵和).

最大子列和,及其扩展最大子矩阵和,都是比较经典的dp,把这两题写在一起,共大家参考学习. ~~~~ lz弱菜啊,到现在还只能写这么水的DP...orz. ~~~~ 题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1003 http://acm.hdu.edu.cn/showproblem.php?pid=1081 题意应该比较好理解,不解释了. 1003: #include<cstdio> #include<iostream> #inc

dp 动态规划 hdu 1003 1087

动态规划就是寻找最优解的过程 最重要的是找到关系式 hdu 1003 题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1003 题目大意:求最大字序列和,其实就是分成 以0结尾的序列 以1结尾的序列 以2结尾的序列 ... 以n结尾的序列 所以以n结尾的序列的最大值就是以n-1结尾的序列的最大值+n的值 或最大值是n的值 关系式: d[i]=max(d[i-1]+a[i],a[i]) d[i]为以i结尾的序列和的最大值,a[i]为第i个数的值 #in

HDU - 1003 - Max Sum &amp;&amp; POJ - 1050 - To the Max (经典DP问题)

题目传送:HDU - 1003 思路:最大子序列和 dp[i]= a[i]   (dp[i-1]<0) dp[i]= dp[i-1]+a[i]   (dp[i-1]>=0) AC代码: #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <cmath> #include <queue> #include

HDU 1003 Max Sum(DP)

题目地址:HDU 1003 DP好弱..先补补DP的基础... 这题就是记录起始点与终止点,然后每当发现一个更大的,就更新.从左往右扫一遍就行了. 代码如下: #include <iostream> #include <cstdio> #include <string> #include <cstring> #include <stdlib.h> #include <math.h> #include <ctype.h> #

HDU 1003 Max Sum 最大连续子序列的和

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