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
12
13
14
15
16
17
18
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:

        # step 0: walk the nums
        # step 1: keep cur_result = max(num, cur_result + num), start from now or keep the result
        # step 2: keep the final result = max(result, cur_result)
        # time complexity: O(n)
        # space complexity: (1)

        result = nums[0]
        cur_result = nums[0]

        for n in nums[1:]:

            cur_result = max(n, cur_result + n)
            result = max(result, cur_result)

        return result

也許你也會想看看