python - 谁能解释这个 "Maxium Subarray"问题？

Question

我曾经在网上看到这个编码问题..

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

...并从 leetcode 用户那里得到了一个解决方案...

def maxSubArray(self, nums: List[int]) -> int:
    sumVal = 0
    ret = 0
    for i in nums:
        sumVal = max(0, sumVal) + i
        ret = max(ret, sumVal)
    return max(nums) if ret == 0 else ret

虽然经过一些“调试”后我也不知道它是如何工作的。

你能解释一下吗？

Answer 1

正如问题所述，它的所有要求都是使用连续元素在子数组中找到可能的最大值，即相邻元素。

这里的做法是一个一个遍历数组，将元素加到总和上，检查是否超过当前最大值，如果超过，则更新最大值。查看每行的内联注释。

def maxSubArray(self, nums: List[int]) -> int: #type hint to return an int value
    sumVal = 0 #keeps the total sum
    ret = 0 #return value
    for i in nums: #iterates through every single value in the list
        sumVal = max(0, sumVal) + i #gets the total sum for the upto the given i value
        ret = max(ret, sumVal) #ret variable is updated with whichever is the max of `ret` or `sumVal`.
    return max(nums) if ret == 0 else ret #retunrs max value of the array if ret = 0; this simply means array is of single element.Else return the value held in `ret`

虽然这段代码并不完整。它不会尝试检查连续值，而只是检查可能的总和。

运行这个，

def maxSubArray(nums):
    sumVal = 0
    ret = 0
    for i in nums:
        sumVal = max(0, sumVal) + i
        ret = max(ret, sumVal)
    return max(nums) if ret == 0 else ret

print(maxSubArray([8,1,-3,4,-1,2,1,-5,4]))

给出 12。参见 here了解更多信息