題目鏈接：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 4Case 2: 7 1 6

思路：對(duì)于每一個(gè)當(dāng)前點(diǎn)都保證相加之后的和比本身大就好了，貪心思想。如果用我注釋掉的方法做超時(shí)，但目前還沒想到怎么優(yōu)化，歡迎評(píng)論|“_”|

代碼如下：

#include<iostream> #include<stdio.h> #define M 100000+5 #define LL long long using namespace std;//int a[M];int main(){int t,ans=0; while(scanf("%d", &t)!=EOF){while(t--){int n,st=1,ed=1,est=1;int sum,x,maxn;scanf("%d%d", &n, &x);sum=maxn=x;for(int i=2; i<=n; ++i){scanf("%d", &x);if(sum+x<x){sum=x;st=i;}else{sum+=x;}if(maxn<sum){maxn=sum;est=st;ed=i;}}/*for(int i=1; i<=n; ++i){//超時(shí) if(a[i]<=0) continue;for(int j=i,k; j<=n ; ++j){//int k;s=0;for(k=1; k<=j; ++k){s+=a[k];if(sum<s){sum=s;st=i;ed=k;} } }}*/ if(ans!=0) printf("\n");printf("Case %d:\n%d %d %d\n",++ans, maxn, est, ed);}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的HD 1003 Max Sum(贪心)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。