LeetCode 筆記 - 53. Maximum Subarray

題目在此 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)

也許你也會想看看