Leetcode # 918. Maximum Sum Circular Subarray

https://leetcode.com/problems/maximum-sum-circular-subarray/

Solution

我們想在「circular array版本的Ａ」中找其maximum sum Subarray
令 B = -A ，只要 A 減去「 B 的maximum sum Subarray」就是答案

注意題目的限制：maximum sum Subarray必須是non-empty
故 len(B) 必須小於 len(A) – 1

 int:
    if len(nums) == 1:
      return nums[0]
    
    def kadane(nums):
      max_ending_here = max_so_far = nums[0]
      for num in nums[1:]:
        max_ending_here = max(num, max_ending_here + num)
        max_so_far = max(max_so_far, max_ending_here)
      return max_so_far
    
    nums_sum = sum(nums)
    neg_nums = [-num for num in nums]
    
    return max(kadane(nums), \
               nums_sum + kadane(neg_nums[1:]), 
               nums_sum + kadane(neg_nums[:-1])) 

我一開始發生的邏輯錯誤

一開始我的想法是
「在nums * 2中使用Kadane's algorithm
在子序列max_ending_here長度超過len(nums)時
消去子序列max_ending_here第一個元素及其後連續的非正整數（0和負數）」

但正確的做法是
「在子序列max_ending_here長度超過len(nums)時
消去子序列max_ending_here第一個元素
並且繼續向後尋找要消除多少個前方連續元素才能使max_ending_here最大
然而這會使得 Time Complexity 多達 O(len(nums) ^ 2)」

Last Updated on 2023/08/16 by A1go