简单的算法-Leet代码-最大子数组

Question

我一直在纠结这件事。

最大子数组简单给定一个整数数组数，找到总和最大的相邻子数组（至少包含一个数字）并返回其总和。

子数组是数组的连续部分。

示例1：

输入:nums = [-2，1，-3，4，-1，2，1，-5，4]输出:6解释:[4，-1，2，1]的和最大= 6。示例2:

输入：nums=[1]输出：1示例3：

输入： 数字 = [5，4，-1，7，8] 输出： 23

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        subarray1=[]
        subarray2=[]
    
        for n in nums:
            subarray1.append(sum(nums[nums.index(n):]))
            nums2=nums[::-1]
            subarray2.append(sum(nums2[nums.index(n):]))
            para1=subarray1.index(max(subarray1))
            para2=len(nums)-subarray2.index(max(subarray2))
            ans=sum(nums[para1:para2])
        
        if sum(nums)>ans :
            ans=sum(nums)
        
        if len(nums)==2 and sum(nums)< nums[0] or nums[1] :
            ans=max(nums)
       
        return ans

我不明白迭代逻辑，视频中的答案是错误的。我的逻辑是创建一个对两边的输入数组求和的数组，并使用这两个数组上最大值的索引来计算出子数组参数的最大和。

当复制到leet代码时，我的答案可能是错误的https://leetcode.com/problems/maximum-subarray/

已经尝试了几个小时，它被标记为简单。我相信有一种简单的迭代方法可以做到这一点，但到目前为止，我搜索的所有内容都是错误的。

Answer 1

这是我的解决方案，尽管当输入列表包含很多元素时，它超出了时间限制。我的想法是尝试每个子列表的总和，并相应地更新最大总和。使用“分而治之”的方法有一种更快，但更复杂的方法：https://leetcode.com/problems/maximum-subarray/discuss/1849465/Divide-and-Conquer-Approach-with-Python

我的解决方案（适用于200/209例，因为超过了时间限制）：

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        max_sum = - 10 ** 4

        for i in range(len(nums)):
            for j in range(i + 1, len(nums) + 1):
                s = sum(nums[i:j])
                if max_sum < s:
                    max_sum = s
        return max_sum

Answer 2

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        for i in range(1, len(nums)):
            if nums[i-1] > 0:
                nums[i] += nums[i-1]
        return max(nums)

这是一个具有恒定空间的2遍O（n）时间复杂度解。

工作原理:我们将每个元素添加到它的前一个元素中，前提是前一个元素大于0(大于或等于也可以)。想法是这样的:如果负数已经设法使它小于0，我们就丢弃前缀，不再关心它们。但是如果剩余一些正值，我们会添加它，因为它比什么都没有好。

最后，我们寻找最大值。

为了使它一次通过，您可以有一个在每次迭代中取最大值的< code>best值。那么你就不需要在数组末尾再次循环来取最大值。

这是通过Kadane的算法，如果你有兴趣进一步阅读它。

Answer 3

其中许多问题都有一个标准的逻辑。假设您知道总数最大的子数组是nums[：n-1]。那么，子数组nums[：n]的最大总数是多少？

有两种可能性:

• 新答案不包含nums[n-1]。在这种情况下，它必须与旧答案相同
• 新答案确实包含nums[n-1]。

因此…实际的算法是您迭代遍历数组，反复向数组添加新元素，并跟踪两个答案：

1. 什么是总数最大的子阵列
2. 包含最后一个元素的总计最大的子数组是什么。（此答案可能与前一个答案相同。

然后，当您将新元素添加到数组的末尾时：

1. 总数最大的子数组是（a）前一个最大的总数或（b）前一个最大的总数，其中包含最后一个元素加上新的最后一个元素，或者（c）只是最后一个元素。选择总数最大的一个。
2. 包含最后一个元素的总数最大的子数组是上面（b）或（c）中较大的一个。