时间戳

首页 > 解决方案 > 谁能解释这个“最大子阵列”问题？

python - 谁能解释这个“最大子阵列”问题？

问题描述

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

给定一个整数数组 nums，找到总和最大的连续子数组（至少包含一个数）并返回它的总和。

例子： 

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

尽管即使经过一些“调试”，我也不知道它是如何工作的。

你能解释一下吗？

标签： python

解决方案

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

这里的方法是一个一个地遍历数组并将元素添加到总和中，并检查它是否超过当前最大值，如果是，则更新最大值。请参阅有关每行功能的内联注释。

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. 请参阅此处以了解更多信息

推荐阅读