题目描述题目要求从一段道路的niceness\texttt{niceness}niceness值序列中找出连续子段的最大和。若最大和为正输出该子段的起始和结束站点编号站点从111开始若有多个子段达到最大和选择长度最长即经过的道路数最多的若长度相同选择起始站点最小的。若最大和不为正输出无解信息。输入格式第一行一个整数bbb表示公交路线的数量。每个路线描述的第一行是一个整数sss2≤s≤200002 \le s \le 200002≤s≤20000表示该路线的站点数。接下来s−1s-1s−1行每行一个整数nin_ini​表示站点iii到i1i1i1之间的niceness\texttt{niceness}niceness值。输出格式对于每条路线输出一行若最大和为正输出The nicest part of route r is between stops i and j。否则输出Route r has no nice parts。样例输入3 3 -1 6 10 4 -5 4 -3 4 4 -4 4 -5 4 -2 -3 -4输出The nicest part of route 1 is between stops 2 and 3 The nicest part of route 2 is between stops 3 and 9 Route 3 has no nice parts题目分析本题的核心是求解最大子段和并记录最优子段的起止位置。由于sss可达200002000020000使用O(s)O(s)O(s)的Kadane\texttt{Kadane}Kadane算法即可。算法遍历每个niceness\texttt{niceness}niceness值维护当前子段和maxCurrent\textit{maxCurrent}maxCurrent及其起止位置。若当前niceness\texttt{niceness}niceness值大于maxCurrent\textit{maxCurrent}maxCurrent则从当前位置开始新的子段。若maxCurrentmax\textit{maxCurrent} \textit{max}maxCurrentmax或maxCurrentmax\textit{maxCurrent} \textit{max}maxCurrentmax且当前子段长度更长则更新最优解。注意点站点编号与道路编号的关系道路nin_ini​连接站点iii和i1i1i1因此子段从站点startstartstart到endendend包含的道路为nstart,nstart1,…,nend−1n_{start}, n_{start1}, \ldots, n_{end-1}nstart​,nstart1​,…,nend−1​。当maxCurrent\textit{maxCurrent}maxCurrent为负时应放弃当前子段从下一个位置重新开始。若所有niceness\texttt{niceness}niceness值均为负则最大和为负输出无解。复杂度分析时间复杂度O(s)O(s)O(s)空间复杂度O(1)O(1)O(1)。代码实现// Jill Rides Again// UVa ID: 507// Verdict: Accepted// Submission Date: 2016-08-21// UVa Run Time: 0.040s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intcases;cincases;for(intr1;rcases;r){ints,niceness;cinsniceness;intmaxniceness,start1,end2;intmaxCurrentniceness,startCurrent1,endCurrent2;s--;for(inti2;is;i){cinniceness;endCurrenti1;maxCurrentniceness;if(nicenessmaxCurrent){startCurrenti,endCurrenti1;maxCurrentniceness;}if(maxCurrentmax||(maxCurrentmaxabs(endCurrent-startCurrent)abs(end-start))){maxmaxCurrent;startstartCurrent,endendCurrent;}}if(max0){coutThe nicest part of route r is between stops ;coutstart and end\n;}elsecoutRoute r has no nice parts\n;}return0;}