lintcode循環數組之連續子數組求和

v 題目：連續子數組求和 II

給定一個整數循環數組（頭尾相接），請找出一個連續的子數組，使得該子數組的和最大。輸出答案時，請分别傳回第一個數字和最後一個數字的值。如果多個答案，請傳回其中任意一個。

v 樣例

 給定 <code>[3, 1, -100, -3, 4]</code>, 傳回 <code>[4,0]</code>.

v 思路

1.如果不是循環數組，求解連續子區間和的思路如下: 首先設一個累加變量和sum和最大值變量maxN，[ld, rd]表示目前正在累加的區間，[lt,rt]表示最大和的區間。從左邊開始一直累加，并初始目前區間[ld, rd]的左右兩端的值。如果在累加之前發現sum&lt;0，那麼更新sum為目前的要累加的數字，并且重置新的區間左右兩端的值(即[ld, rd]的值)。另外在累加的過程中，如果sum的值大于maxN，更新maxN的值，并且更新最大值區間(即[lt, rt]改變成[ld, rd])。

2.現在是循環數組，最大和的區間可能會出現在數組的兩端，也就是數組的左邊一段和數組的右邊的一段組成。那麼中間的那一部分就是區間和最小的部分。假設一下左端區間[l1, r1]和右端區間[l2, r2]組成最大和的區間，如果[r1+1, l2-1]不是最小和區間，那麼存在區間[lx, rx]的和比[r1+1, l2-1]區間和更小（其中有lx&gt;r1+1, rx&lt;l2-1），那麼也就是區間[r1+1, lx-1](或者[rx+1, l2-1])和一定大于0，這樣必然會導緻左端區間[l1, r1]區間和 + 區間[r1+1, lx-1]和更大。是以區間[r1+1, l2-1]一定是最小區間和。

如 <code>[-1, 2, -1, 2, -1, 10, -100, 10, 9, 8, 7]</code>, 這個例子中，最小的區間和是-100，區間[6, 6], 區間[7, 5]（注意是循環數組）就是最大的區間和。

v AC代碼