首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Q53 Maximum Subarray

Q53 Maximum Subarray

作者头像
echobingo
发布2018-04-25 16:46:18
6130
发布2018-04-25 16:46:18
举报

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4], the contiguous subarray [4,-1,2,1] has the largest sum = 6.

解题思路:

此题为动态规划中很经典的一个题目,具体做法是新建一个列表,记录最大子段和。如果子段和为负值或者子段和加上一个数负值,则重新开始计算子段和,否则,进行字段和的累加。最后,返回新建字段和列表中的最大值。时间复杂度为O(n),空间复杂度也为O(n)。

Python实现:
# 动态规划
class Solution:
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 0:
            return 0 
        maxl = []  # 记录最大子段和
        maxl.append(nums[0])
        for i in range(1, len(nums)):
            if maxl[i-1] < 0 or maxl[i-1] + nums[i] < 0:  # 如果子段和为负值或者子段和加上一个数为负值,则把当前数作为下一个子段和的开始数值
                maxl.append(nums[i])
            else:  # 否则,累积子段和
                maxl.append(maxl[i-1] + nums[i])
        return max(maxl)

a = [-2,1,-3,4,-1,2,1,-5,4]
b = Solution()
print(b.maxSubArray(a))  # 6 # [4,-1,2,1]
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2018.02.28 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 解题思路:
  • Python实现:
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档