主題
題目連結：
題目意譯：
給定一個長度為 n 個環形整數陣列 nums，回傳 nums 中一個非空子陣列之元素總和最大值。
一個環形陣列代表著該陣列的結尾與開頭是相連的。更正式地說，nums[i] 的下一個元素為 nums[(i + 1) % n]，而 nums[i] 的前一個元素為 nums[(i - 1 + n) % n]。
一個子陣列應只包含 nums 中每一個元素最多一次。更正式地說，對於一個子陣列 nums[i], nums[i + 1], ……, nums[j]，不存在任何的 i ≦ k1 、 k2 ≦ j 使得 k1 % n == k2 % n。
限制：
n == nums.length
1 ≦ n ≦ 3 × 10 ^ 4
-3 × 10 ^ 4 ≦ nums[i] ≦ 3 × 10 ^ 4
範例測資：
範例 1：
輸入： nums = [1,-2,3,-2]
輸出： 3
解釋： 子陣列 [3] 有著最大總和值 3。
範例 2：
輸入： nums = [5,-3,5]
輸出： 10
解釋： 子陣列 [5,5] 有著最大總和值 5 + 5 = 10。
範例 3：
輸入： nums = [-3,-2,-3]
輸出： -2
解釋： 子陣列 [-2] 有著最大總和值 -2。
解題思維：
基本上跟這題一致。但是該題採取的策略之時間複雜度最糟會是 O(n ^ 2)，所以我們需要做得更好一點。
首先先做一次普通的最大子陣列和（Maximum Subarray Problem），也就是沒有頭尾相連的特質。這邊跟上面的鏈結中提到的一致，沒有變化。
接著就是要考慮頭尾相連了，可以看到此時可以把「子陣列」看做是某個前綴（Prefix）加上某個後綴（Suffix）（注：整個陣列作為子陣列的上面已經考慮過了，所以這邊不用再考慮一次）。
此時可以看到，如果我們可以對任意一個前綴和 nums[0] + nums[1] + …… + nums[L] 知道以下後綴（們）：
nums[L + 2] + nums[L + 3] + …… nums[n - 1]、
nums[L + 3] + nums[L + 4] + …… nums[n - 1]、
nums[L + 4] + nums[L + 5] + …… nums[n - 1]、
……
中哪一個總和最大，則我們便可以藉由掃過每一個前綴和來知道哪個頭尾相連的子陣列之總和是最大的。
那要怎麼找出哪個後綴最大呢？
可以看到對於每個前綴和最後一項 nums[L]，後綴最遠可以從結尾延伸到 nums[L + 2]（如果延伸到 nums[L + 1]，則就是整個陣列。而如先前所述，這個情況已經考慮過）。
因此如果我們可以直接「問」L + 2 這個位置就知道的話則可以達成所需的效果。而我們可以先做一次後綴和（基本上跟前綴和一樣求法，如這題）。所以我們現在知道每一個後綴和之值，因此令 S[i] = nums[i] + nums[i + 1] + …… nums[n - 1]。
則我們可以再定義一個陣列 M，其中
M[i] = max(S[i], S[i + 1], ……, S[n - 1]) = max(S[i], M[i + 1])
（對於 M[n - 1] 即為 S[n - 1]，也就是 nums[n - 1]）。
而此時可以看到這個 M 陣列就是在問從位置 i 之後開始的後綴何者最大。因此對於每個前綴和之結尾 nums[L]，直接存取 M[L + 2] 便可以知道所求最大後綴和。
而我們可以看到上述所有操作都可以在線性時間，也就是 O(n) 時間內達成。因此總時間複雜度也是 O(n)。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
