[FGISC。Nanro] 未來開端

演算法：DP之最大連續元素和

翻譯by 南一中seanwu 轉自sa同學的版

---

Problem:

        Jill是個很容易自嗨的人。有一天她要騎自行車走一條有許多站牌的路，

    而在站與站之間的路上會得到不同的不同的「嗨度」。然後她想知道在那一站

    到哪一站之間，她可以擁有最大的「嗨度」，兩站之間的嗨度定義為這兩站之

　　間路徑的嗨度總合。

　　　　如果有兩組不同的起迄點，取兩站之間差的距離（站數）較多的那一組；

    如果又相同，取起點較小者。

        輸入第一行有一整數表示有幾組測資，每組測資的第一個數表示這條路有

    幾站，其餘為兩站之間的嗨度，不會有嗨度等於 0。

        如果最大的嗨度不大於 0，請輸出 has no nice parts

Example Input:

2
4
  -2
  -3
  -4
4
  -1
  -2
   1

Example Output:

Route 1 has no nice parts
The nicest part of route 2 is between stops 3 and 4

---

這又是最大連續元素和的題目啦～
基礎的請看先前那篇http://blog.pixnet.net/aikosenoo/post/7442660

這題只是做點變化
數字給的是站與站之間的距離
比如說他給
3
2
4
就代表有三個站，1-2之間的距離2 2-3之間的距離4
本題要輸出最大距離的兩個站
如果相同距離就輸出站編號差最大的
如果連這個也都相同就輸出起頭編號最小的

可以利用一些暫存的變數判斷與處理
熟悉MCS的應該不難想～
有問題的歡迎發問～