题目描述
题目要求从一段道路的niceness\texttt{niceness}niceness值序列中，找出连续子段的最大和。若最大和为正，输出该子段的起始和结束站点编号（站点从111开始）；若有多个子段达到最大和，选择长度最长（即经过的道路数最多）的；若长度相同，选择起始站点最小的。若最大和不为正，输出无解信息。
输入格式
第一行一个整数bbb，表示公交路线的数量。每个路线描述的第一行是一个整数sss（2≤s≤200002 \le s \le 200002≤s≤20000），表示该路线的站点数。接下来s−1s-1s−1行，每行一个整数nin_ini，表示站点iii到i+1i+1i+1之间的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，则从当前位置开始新的子段。
- 若maxCurrent>max\textit{maxCurrent} > \textit{max}maxCurrent>max，或maxCurrent==max\textit{maxCurrent} == \textit{max}maxCurrent==max且当前子段长度更长，则更新最优解。
注意点
- 站点编号与道路编号的关系：道路nin_ini连接站点iii和i+1i+1i+1，因此子段从站点startstartstart到endendend包含的道路为nstart,nstart+1,…,nend−1n_{start}, n_{start+1}, \ldots, n_{end-1}nstart,nstart+1,…,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//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intcases;cin>>cases;for(intr=1;r<=cases;r++){ints,niceness;cin>>s>>niceness;intmax=niceness,start=1,end=2;intmaxCurrent=niceness,startCurrent=1,endCurrent=2;s--;for(inti=2;i<=s;i++){cin>>niceness;endCurrent=i+1;maxCurrent+=niceness;if(niceness>maxCurrent){startCurrent=i,endCurrent=i+1;maxCurrent=niceness;}if(maxCurrent>max||(maxCurrent==max&&abs(endCurrent-startCurrent)>abs(end-start))){max=maxCurrent;start=startCurrent,end=endCurrent;}}if(max>0){cout<<"The nicest part of route "<<r<<" is between stops ";cout<<start<<" and "<<end<<'\n';}elsecout<<"Route "<<r<<" has no nice parts\n";}return0;}
