MaxSubarray最大子序和问题
MaxSubarray最大子序和问题
生信编程日常
修改于 2023-09-21 15:39:01
修改于 2023-09-21 15:39:01
回顾leetcode原来做过的题，看到了经典的最大子序和问题，收藏了一个好回答。 这个问题是这样的（https://leetcode.com/problems/maximum-subarray/ ）： Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. 就是给一组整数，找到一组连续的子序列，让子序列的和最大，并且返回最大和。 比如说： 输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 子序列[4,-1,2,1]有最大的和6.
原来是这样做的：
class Solution(object):
def maxSubArray(self, nums):
flag = False
for num in nums:
if num > 0:
flag = True
if flag == True:
s = 0
m = 0
for num in nums:
s += num
if s > 0 :
if s > m:
m = s
else:
s = 0
return m
else:
return max(nums)运行时间28ms，在时间上可以超过100%的python答案，不过怎么看怎么罗里吧嗦，而且遍历了两遍。发现在讨论区有个很精简的回答：
class Solution:
def maxSubArray(self, nums):
for i in range(1, len(nums)):
if nums[i-1] > 0:
nums[i] += nums[i-1]
return max(nums)想法非常巧妙。
欢迎关注公众号～
生信编程日常
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读