题目链接:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=448
典型的最大子段和问题。
#include<iostream> using namespace std; int main() { int testNumber; //测试的数目 cin>>testNumber; for(int index=1;index<=testNumber;index++) //循环测试每组数据 { int max=0,sum=0,tempNumber=0; int tempStart=0; int start=0,end=0; int number; cin>>number; for(int i=0;i<number-1;i++) { cin>>tempNumber; sum+=tempNumber; if(sum<0) //小于0的话暂时放弃之前的值,将下一个值作为起点 { tempStart=i+1; sum=0; } if(sum>max||(sum==max&&start==tempStart))//只有在大于最大值的时候才会更新 { //一定要注意第二种情况, //If more than one segment is maximally nice, // choose the one with the longest cycle ride (largest j-i). //To break ties in longest maximal segments, //choose the segment that begins with the earliest stop (lowest i) max=sum; start=tempStart; end=i; } } if(max==0) cout<<"Route "<<index<<" has no nice parts"<<endl; else cout<<"The nicest part of route "<<index<<" is between stops "<<start+1<<" and "<<end+2<<endl; } return 0; }