首页 > ACM题库 > HDU-杭电 > HDU 1003 Max Sum-动态规划-[解题报告] C++
2013
11-26

HDU 1003 Max Sum-动态规划-[解题报告] C++

Max Sum

问题描述 :

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.

输入:

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).

输出:

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.

样例输入:

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

样例输出:

Case 1:
14 1 4

Case 2:
7 1 6

http://acm.hdu.edu.cn/showproblem.php?pid=1003

初识dp,大问题是求出总序列的最大和,而每个数都有加到前面作为前面已经加好的和的增量和自己独立成为一个“最大和”的选择,在这两个选择中的最大和就是局部的最大和,而保存好第一个最大和,将整个序列的所有局部最大和都求解出来,就能得到全列的最大和

#include<stdio.h>
int main()
{
    int i,ca=1,t,s,e,n,x,now,before,max;
    scanf("%d",&t);
    while(t--)
    {
       scanf("%d",&n);
       for(i=1;i<=n;i++)
       {
         scanf("%d",&now);
         if(i==1)//初始化 
         {
            max=before=now;//max保留之前算出来的最大和,before存储目前在读入数据前保留的和,now保留读入数据  
            x=s=e=1;//x用来暂时存储before保留的和的起始位置,当before>max时将赋在s位置,s,e保留最大和的start和end位置 
         }
         else {
             if(now>now+before)//如果之前存储的和加上现在的数据比现在的数据小,就把存储的和换成现在的数据,反之就说明数据在递增,可以直接加上 
             {
                before=now;
                x=i;//预存的位置要重置 
             }       
             else before+=now;
              }
         if(before>max)//跟之前算出来的最大和进行比较,如果大于,位置和数据就要重置 
           max=before,s=x,e=i;
       }
       printf("Case %d:\n%d %d %d\n",ca++,max,s,e);
       if(t)printf("\n"); 
    }
    return 0;
}

 


  1. 你完全理解错了,说的是位置不是数字,而且第一个数是代表你后面可以输入多少数,并没有参与求和

  2. 嗯 分析得很到位,确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样:push时,比较要push的elem和辅助栈的栈顶,elem<=min.top(),则min.push(elem).否则只要push(elem)就好。在pop的时候,比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();},否则{stack.pop();}.

  3. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的