一列數(shù)構(gòu)成一個環(huán)（首尾相接），求最大子序列的和
線性數(shù)列的最大子序列的和是DP基本題，改為環(huán)形后的比較容易想到的思路是先在原數(shù)列上做一遍DP，再考慮最大子序列由最左和最后幾個數(shù)構(gòu)成的情況
可以只做一遍DP，思路參考->https://leetcode.com/problems/maximum-sum-circular-subarray/solutions/178422/One-Pass/
轉(zhuǎn)化為在一遍循環(huán)內(nèi)考慮最大子序列和最小子序列的情況
1 #918
2 #Runtime: 360 ms (Beats 93.81%)
3 #Memory: 17.1 MB (Beats 54.87%)
4
5 class Solution(object):
6 def maxSubarraySumCircular(self, nums):
7 """
8 :type nums: List[int]
9 :rtype: int
10 """
11 t_max, t_min, cnt, ans_max, ans_min = 0, 0, 0, nums[0], nums[0]
12 for i in nums:
13 t_max = max(t_max + i, i)
14 t_min = min(t_min + i, i)
15 ans_max = max(ans_max, t_max)
16 ans_min = min(ans_min, t_min)
17 cnt += i
18 if ans_max > 0:
19 return max(ans_max, cnt - ans_min)
20 return ans_max