給一個環形陣列 A，要找出總和最大的子陣列。
這題蠻有意思的，讓我沒有順利解出來，有想到好幾種可能，看了別人的解法，發現是用最大最小的方式。
但我想到這方法的當下，沒有去進一步思考。
官方有 Solution ，內有四種解法，但我還是照步調去走從未知去導出解法的思維分析。
如果會做陣列中子陣列最大總和，那環形的也只是稍做變化。
要如何後面接回前面？這是第一個要解決的問題。
對於一個陣列來說，用Python是可以再添加一個一樣的，達到 2n 的長度，在 n - 1 位置之後，又會回到開頭的值。
但由於限制每個元素只能被取一次，這作法可能會讓一元素被選中二次(如全部為正的)，並不是一種簡單可行的方法。
又或者弄 linked list ，然後作 DP 以各元素的選取保存每一位置的最大值總和。這能避免重複，但寫來會有點麻煩。
照著 Hint ，要用「 Kadane's algorithm 」， 然而這不是算環形的陣列，需要改良才能用上。如果只跑一遍陣列，那也不會碰到同元素被選二次的狀況。
如果最大值落於陣列間，最後的位置不是 n - 1，那 Kadane's algorithm 就可以找出正解。
但最後位置有碰到 n - 1，那麼就會接回開頭去找的需求。
再思考，如果目前正計算最大的子陣列，沒到計算結束前是不知道目前的是否處在最大子陣列中。而且 Kadane's algorithm 的方式也沒有保存位置，判斷最後位置並不是好的方法。
但以結果回推，最大子陣列以外的元素加總就是最小子陣列。
因此取得最小子陣列的總和，用整個數列的總和去減它，也可以得到最大子陣列的總和。
如果最小子陣列在陣列之間，那最大子陣列會是環形接起的。
因此所求在「陣列(沒有環)子陣列最大總和」或「總合減陣列子陣列最小總和」中，兩者取大。
但這樣子有一個狀況，如果是遞減數列，最小總和會是全體元素集合，而總和減去它會是 0 ，也比最大總和還大。
因此，如果 總和 == 子陣列最小總和 ，那只能回傳前者。
class Solution:
def maxSubarraySumCircular(self, A: List[int]) -> int:
min_now = max_now = A[0]
nmin = nmax = nsum = A[0]
for num in A[1:]:
min_now = min(num, min_now + num)
nmin = min(nmin, min_now)
max_now = max(num, max_now + num)
nmax = max(nmax, max_now)
nsum += num
if nsum == nmin: return nmax
return max(nsum - nmin, nmax)
C#
public class Solution {
public int MaxSubarraySumCircular(int[] A) {
int min_now = A[0]; int max_now = A[0];
int nmin = A[0]; int nmax = A[0]; int nsum = A[0];
for(int i = 1; i < A.Length; i++)
{
int num = A[i];
min_now = (min_now + num < num) ? min_now + num : num;
nmin = nmin < min_now ? nmin : min_now;
max_now = (max_now + num > num) ? max_now + num : num;
nmax = nmax > max_now ? nmax : max_now;
nsum += num;
}
if(nsum == nmin){return nmax;}
return (nmax > nsum - nmin) ? nmax : nsum - nmin;
}
}