Loading......Next.

生来介为忙一场

 

HDOJ 1003 Max Sum 非递归算法(很巧妙~~~)【转】

/*Max Sum
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 37083    Accepted Submission(s): 7979

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
*/

#include<iostream>
using namespace std;
int main(){
    int N;cin>>N;
    for(int k=1;k<=N;k++){
        if(k-1)cout<<endl;
        int n;cin>>n;
        int i,j,beg,end,max=-11111111,sum,fig;
        for(i=j=1,sum=0;j<=n;j++){
            cin>>fig;
            sum+=fig;
            if(sum>max){max=sum;beg=i;end=j;}//a只在此处改变beg,和end 的大小
            if(sum<0){i=j+1;sum=0;}//如果sum小于零了,那么说明刚加进来的fig特别的小(小到这种“特殊”的程度)
            //试探性的以次为起点,如果后来的sum 比max 大,则前面的一连串就毫无意义(因为加上一个负值肯定会变小的)
        }
        cout<<"Case "<<k<<":\n";
        cout<<max<<" "<<beg<<" "<<end<<endl;
    }
    return 0;
}
 
说白了是一种贪心算法:

Int MaxSubsequenceSum(const int A[], int N)

{

       int ThisSum, MaxSum, j;

       ThisSum = MaxSum = 0;

       For(j=0; j < N; j++)

{

              ThisSum += A[j];

              If (ThisSum > MaxSum)

                     MaxSum = ThisSum;

              Else if(ThisSum < 0)

                     ThisSum = 0;

}

return MaxSum;

}

posted on 2011-06-11 23:21 bersaty 阅读(2126) 评论(3)  编辑 收藏 引用 所属分类: HDOJ 做题报告

评论

# re: HDOJ 1003 Max Sum 非递归算法(很巧妙~~~)【转】 2013-04-29 15:21 王者

当测试数据都为负数时,输出好像不对吧!
  回复  更多评论   

# re: HDOJ 1003 Max Sum 非递归算法(很巧妙~~~)【转】 2013-04-29 15:43 王者

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int a[100001];
void biggest(int len){
int i,max,result,start,end,s,e;
result=-1000; max=0;
s =1 ; e =1;
start =1 ; end=1;
for(i=1;i<=len;i++){
if(max>=0) {max+=a[i];e=i;}
else if(max<0) {max=a[i];s=i;e=i;}
if(max>result) {start=s;end=e;result=max;}
}
cout<<result<<" "<<start<<" "<<end<<endl;
}
int main()
{
int n,m,len,i;
cin>>n;
m=n;
while(n--){
memset(a,0,sizeof(a));
cin>>len;
for(i=1;i<=len;i++)
cin>>a[i];
printf("Case %d:\n",m-n);
biggest(len);
if(n>=1)
cout<<endl;
}
return 0;
}
  回复  更多评论   

# re: HDOJ 1003 Max Sum 非递归算法(很巧妙~~~)【转】 2013-04-29 15:44 王者

这个是我另外看到的,挺符合题意的。  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

统计

常用链接

留言簿

随笔分类

随笔档案

友情链接

搜索

最新评论

阅读排行榜

评论排行榜