上一篇看這裡：[LeetCode]各種Max subarray問題-1
1191. K-Concatenation Maximum Sum
題意: 將一個array重複拼接K次後，找一個subarray，使得該subarray有最大的和。
Input: arr = [1,2], k = 3
Output: 9
1. 把所有array重複k次後做kadane’s algo，但會TLE，因為資料(10^5) *k(10^5)太大了
- 考慮以下幾種case:
- k == 1的時候答案就是kadane’s
- k>=2且array total sum>0，此時越多的array有助於增加長度，答案會是
- [第一個array的最大後綴和] + (k-2)*total_sum + [最後一個array的最大前綴和]
k>=2且array total sum <= 0，此時array越多也沒有幫助，就直接拼接兩次做kadane’s algo
- 之所以拼接兩次是要顧慮到如果答案是一端的尾巴 + 一端的頭的情況
這次的code弄了好久還是貼不上來，只能說wordpress支援code的功能真的爛到爆，所以有需要的去github上看吧。