一列数构成一个环(首尾相接),求最大子序列的和
线性数列的最大子序列的和是DP基本题,改为环形后的比较容易想到的思路是先在原数列上做一遍DP,再考虑最大子序列由最左和最后几个数构成的情况
可以只做一遍DP,思路参考->https://leetcode.com/problems/maximum-sum-circular-subarray/solutions/178422/One-Pass/
转化为在一遍循环内考虑最大子序列和最小子序列的情况
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