简易算法-Leetcode-最大子数组

Question

努力解决这个问题。

最大子数组简单给定一个整数数组 nums，找到具有最大和的连续子数组（至少包含一个数）和 return 它的和。

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

示例 1：

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

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

输入：nums = [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

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

我的答案在复制到 leet 代码时据说是错误的 https://leetcode.com/problems/maximum-subarray/

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

Answer 1

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) 时间复杂度解决方案，常数为 space。

工作原理：我们将每个元素添加到其前身，前提是前身大于 0（大于或等于也可以）。想法是这样的：如果负数设法使其小于 0，我们将丢弃前缀并且不再关心它们。但是，如果剩余一些正值，我们会添加它，因为它总比没有好。

最后我们寻找最大值。

为了使其通过一次，您可以只使用一个 best 值，该值在每次迭代时都取最大值。然后你就不需要在最后再次遍历数组来取最大值。

顺便提一下Kadane's algorithm，如果您有兴趣进一步阅读。

Answer 2

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

我的解决方案（由于 Time Limit Exceeded 而在 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 3

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

有两种可能：

新答案不包含nums[n-1]。在那种情况下，它必须与旧答案相同
新答案是否包含nums[n-1]。

所以。 . . 实际算法是迭代遍历数组，重复向数组添加新元素，并跟踪两个答案：

总数最大的子数组是什么
包含最后一个元素的总和最大的子数组是什么。（这个答案可能和上一个一样。）

当您将新元素添加到数组末尾时：

总数最大的子数组是 (a) 前一个最大总数或 (b) 前一个包含最后一个元素加上新的最后一个元素的最大总数或 (c) 只是最后一个元素。选择总数最大的那个。
包含最后一个元素的总和最大的子数组是上面的 (b) 或 (c) 中较大的一个。

简易算法-Leetcode-最大子数组

Easy algorithm-Leet code- Maximum sub array

python

algorithm

data-structures