不知道是什麼是卡丹算法的建議先別看下去了

先去寫 d784. 一、連續元素的和

本文預設你已經會寫卡丹算法

(其他方式應該會 TLE)

--

不考慮觀眾席是環形的話，完全可以當成最大子數列和問題看待

只要寫一套卡丹算法即可

但問題就在於有環

我會的作法有兩個

暴力卡丹

一樣是只要把卡丹算法的模板放進來就可以，但重複循環 n 次

每次循環都選不同的位置開始，繞行一周後結束

最後取最大值就是答案

時間複雜度 O(n^2)

環形卡丹

先不管有沒有環，在最大子數列和問題中，我們只關注一部分的數字

那各位有想過在最大子數列之外的部分有什麼意義嗎？

其實在最大子數列之外的部分就是最小子數列

現在想像一下這就是一個可以循環的陣列

當最大子數列的範圍不會通過邊緣時，那答案就是一般的最大數列和

你平常怎麼算卡丹算法，答案就怎樣算

但有個比較極端的情況是下面這樣

最大子數列的範圍會通過邊緣，繞一圈

這時候就無法透過一般的卡丹算法得到正確結果了

此時若我們有計算「最小子數列和」的話，就只需要將陣列所有元素的總和減掉最小子數列和，便可得到答案。

實作最小子數列和其實很簡單，只需要將原本的卡丹算法反過來做

在原本的卡丹算法中，我們會不斷的紀錄區間最大值

這邊只需要反過來，不斷紀錄區間最小值就可以了

時間複雜度: O(n)

--

參考答案: gist(python) (包含兩個版本的算法)

題解出處: LeetCode 918. Maximum Sum Circular Subarray | Solutions | Weird Kadane || Explanation With Images  

(對，我其實只是把它翻譯成中文而已) 

其實還有不用卡丹的 O(n^3) 暴力解，但太慢了，就不細說