python 我应该如何得到具有最大和的子数组？

to94eoyn 于 2023-05-21 发布在 Python

关注(0)|答案(1)|浏览(80)

这个问题是关于leetcode 53的。我把这个问题扩展了一点，返回具有最大和的子数组。
例如，对于list = [-2,1,-3,4,-1,2,1,-5,4]，我应该得到max_subarray = [4,-1,2,1]。
我的代码附在下面。我得到的结果是[4,-1,2,1,-5,4]，也就是cur_array。我不知道我做错了什么。

def maxSubarray(self, list):

    cur_sum = 0
    max_sum = list[0]
    max_subarray = []
    cur_array = []
    for i in range(len(list)):
        cur_sum += list[i]
        cur_array.append(list[i])
        if max_sum < cur_sum:
            max_subarray = cur_array
            max_sum = cur_sum

        if cur_sum < 0:
            cur_sum = 0
            cur_array.clear()
    return max_subarray

它总是给我cur_array。如何修复我的代码？

python

来源：https://stackoverflow.com/questions/76295256/how-should-i-get-the-subarray-with-maximum-sum

1条答案

按热度按时间

myzjeezk1#

这是我对原始问题的解决方案，它击败了99.73%。您需要做的是跟踪索引i，其中获得了最大和。从该索引开始，您可以轻松找到sum等于max sum的子数组。

import sys

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        s = 0
        max_sum = -sys.maxsize
        for i in range(len(nums)):
            s = nums[i] + (s if s > 0 else 0)        
            max_sum = max(max_sum, s)
            
        return max_sum

赞(0）回复(0）举报 2023-05-21

我来回答

python 我应该如何得到具有最大和的子数组？

1条答案

相关问题

热门标签

最新问答