前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode刷题DAY 19:最大子序和

LeetCode刷题DAY 19:最大子序和

作者头像
三猫
发布2020-05-26 17:26:42
2730
发布2020-05-26 17:26:42
举报
文章被收录于专栏:机器学习养成记

⭐️⭐️⭐️

1

题目描述

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。如输入[-2,1,-3]返回1。

2

题解

思路:动态规划

  • 第一步,找到中间状态:此处中间状态st[i]表示第i个元素结尾的子数组最大和。
  • 第二步,确定状态转移:nums[i]加上一个正数和才会变大,不然还是另起炉灶更有可能得到更大的和。所以当st[i-1]为正数时,st[i]=st[i-1]+nums[i],否则st[i]=nums[i]。
代码语言:javascript
复制
class Solution:    def maxSubArray(self, nums: List[int]) -> int:        st = nums[0]        for i in range(1,len(nums)):          st.append(max(nums[i],max_list[i-1]+nums[i]))        return max(st)

官方解题视频中给了两个思路,一个是贪心算法:若当前指向元素之前的和小于0,则丢掉当前元素之前的序列;另一个是动态规划:若前一个元素大于0,则将其加到当前元素上。emmm....感觉两种思路很像,不是特别理解本质区别,有兴趣的一起来讨论~


本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-05-18,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 机器学习养成记 微信公众号,前往查看

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

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

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