507 - Jill Rides Again

吉兒喜歡騎著她的折疊式腳踏車兜風，她會帶著腳踏車搭上公車，然後選擇一個停靠站下車之後，開始沿著公車行駛路徑騎著她的腳踏車，然後在另一個停靠站搭公車回家。事實上，她會從公車行駛路線上的停靠站中選擇起點與終點來騎車。
兩個相鄰停靠站間的路線景色有好有壞，吉兒對停靠站間的每一小段路的喜好程度並不相同，我們用"偏好值"來表示，偏好值愈大表示吉兒愈喜歡騎那一段路。偏好值為正或負值，但不為零。由於吉兒會從某一個停靠站下公車之後，沿路騎腳踏車，然後再到之後的停靠站搭車回家，她希望她騎的那一段路之偏好值之總和最大，本題會給你各站牌間所有路段的偏好值，請你幫吉兒選擇起點站與終點站，使得路線上之偏好值總和最大化。

Input

輸入會有多組測試資料，分別為公車路線資料訊。輸入的第一列有一個整數 b 表示公車路線總數，接下來共有 b 組公車路線。每組路線的第一列會給定站牌總數 s (2 <= s <= 20,000)，之後會有 s-1 列，每列分別表示站牌間路段的偏好值，以 ni 表示(1 <= i < s)。

Output

請針對每組測試資料 r (1 <= r <= b)，輸出起點站 i 與終點站 j，使得 i j 之間的路徑之偏好值總合最大化，即 max = n(i) + n(i+1) + ... + n(j-1)。若有多組符合要求的路徑，請輸出 j - i 最大的那組，若還是有多組選擇，請輸出 i 值最小的那組，其輸出格式為：
The nicest part of route r is between stops i and j

然而，如果最佳路徑之偏好值總合小於或等於零，請輸出：
Route r has no nice parts

Sample Input 

3
3
  -1
   6
10
   4
  -5
   4
  -3
   4
   4
  -4
   4
  -5
4
  -2
  -3
  -4

Sample Output 

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

原文出處