题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=1003
复制代码
#include <iostream>
#include <vector>
using namespace std;
int MaxSubSum(const vector<int>& v,int& start,int& end)
{//求最大子序列和
int maxSum = -2000,thisSum = 0,i,t=0;
for(i=0;i<v.size();++i)
{
thisSum += v[i];
if(thisSum>maxSum)
{
maxSum = thisSum;
start = t;
end = i;
}
if(thisSum<0)
{
thisSum = 0;
t = i+1;
}
}
return maxSum;
}
int main(int argc, char *argv[])
{
int caseNum,curCase=0,nNum,temp,maxSum=0,start=0,end=0;
cin>>caseNum;
do
{
curCase++;
cin>>nNum;
vector<int> v;
for(int i=0;i<nNum;++i)
{
cin>>temp;
v.push_back(temp);
}
cout<<"Case "<<curCase<<":"<<endl;
maxSum = MaxSubSum(v,start,end);
cout<<maxSum<<" "<<start+1<<" "<<end+1<<endl;
if(curCase<caseNum)
cout<<endl;
}while(curCase<caseNum);
return 0;
}
本文转自Phinecos(洞庭散人)博客园博客，原文链接：http://www.cnblogs.com/phinecos/archive/2007/12/23/1011448.html，如需转载请自行联系原作者
