HDU1003 最大子序列和问题

题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=1003

<!--<br /><br />Code highlighting produced by Actipro CodeHighlighter (freeware)<br />http://www.CodeHighlighter.com/<br /><br />-->#include<iostream>

#include<vector>

usingnamespacestd;

intMaxSubSum(constvector<int>&v,int&start,int&end)

{//求最大子序列和

intmaxSum=-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;

}

}

returnmaxSum;

}

intmain(intargc,char*argv[])

{

intcaseNum,curCase=0,nNum,temp,maxSum=0,start=0,end=0;

cin>>caseNum;

do

{

curCase++;

cin>>nNum;

vector<int>v;

for(inti=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);

return0;

}