LeetCode 筆記 - 53. Maximum Subarray

Posted on

題目在此 53. Maximum Subarray

給一個數列，找出相加起來最大值的區段

解題思維

這裡就要提到經典演算法 Kadane’s algorithm 了
簡單又優美的式子 (著迷)

整個演算法核心是持續把 index - 1 的值加到目前的 index
如果 index - 1 是負的就不加，因為只會減少從 index 開始的 sub array 的最大值

原始演算法使用 Python 描述如下

1
2
3
4
5
6
def max_subarray(A):
    max_ending_here = max_so_far = A[0]
    for x in A[1:]:
        max_ending_here = max(x, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

程式碼

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        
        if (size := len(nums)) == 1:
            return nums[0]
        
        for i in range(1, size):
            if nums[i - 1] > 0:
                nums[i] += nums[i - 1]
                
        return max(nums)

也許你也會想看看