Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
一列数构成一个环(首尾相接),求最大子序列的和


线性数列的最大子序列的和是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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理