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