Leetcode专题[数组]-53-最大子数组和

指针大冒险
• 阅读 758

力扣连接:https://leetcode-cn.com/probl...
解题思路:

  1. 看到题的第一眼,只要状态是需要动态决定的,那么大概率就是DP动态规划了
  2. 动态规划基本上是需要三架马车或者三板斧来决定的
    (1)确定数组元素的意义:即dp[]数组是什么含义
    (2)定义数组元素间的关系式,即状态转移方程:即 dp[n] = dp[n-1] + x
    (3)确定初始值:学过数学归纳法的都知道,虽然我们知道了数组元素之间的关系式,如dp[n] = dp[n-1] + dp[n-2],但是我们需要知道最开始的值,dp[1]和dp[2]的值,这就是所谓的初始值

3.回到这道题本身:(1)动态数组元素的意义:dp[i](0 <= i <= n)表示在下标为i的时候,0~i之间数组元素和的最大值 (2)状态转移方程:dp[i] = dp[i - 1] + nums[i],考虑到数组中会有负数,那么方程进一步为:dp[i] = max(dp[i - 1] + nums[i], nums[i]) (3)初始值:由于初始值肯定是从数组第一个元素开始,所以初始值应该为数组第一个元素的值,那么求和就从第二个下标开始遍历

func maxSubArray(nums []int) int {
    max := nums[0]  // 初始值
    for i := 1; i < len(nums); i ++ {
        if nums[i] + nums[i -1] > nums[i] {  // 状态转移方程
            nums[i] += nums[i-1]
        }
        if nums[i] > max {
            max = nums[i]
        }
    }
    return max
}
点赞
收藏
评论区
推荐文章
Wesley13 Wesley13
3年前
Java开发者容易犯的十个错误
!(https://oscimg.oschina.net/oscnet/c9f00cc918684fbe8a865119d104090b.gif)Top1.数组转换为数组列表将数组转换为数组列表,开发者经常会这样做:\java\List<StringlistArrays.asList(arr);Arr
Stella981 Stella981
3年前
SpringBoot整合Redis乱码原因及解决方案
问题描述:springboot使用springdataredis存储数据时乱码rediskey/value出现\\xAC\\xED\\x00\\x05t\\x00\\x05问题分析:查看RedisTemplate类!(https://oscimg.oschina.net/oscnet/0a85565fa
Wesley13 Wesley13
3年前
mysql设置时区
mysql设置时区mysql\_query("SETtime\_zone'8:00'")ordie('时区设置失败,请联系管理员!');中国在东8区所以加8方法二:selectcount(user\_id)asdevice,CONVERT\_TZ(FROM\_UNIXTIME(reg\_time),'08:00','0
Stella981 Stella981
3年前
LeetCode 227场周赛题解
【GiantPandaCV导语】这是LeetCode的第227场周赛的题解,本期考察的知识点有「暴力,字符串,二进制枚举」等等。比赛链接https://leetcodecn.com/contest/weeklycontest227/题目一:检查数组是否经排序和轮转得到
Easter79 Easter79
3年前
SpringBoot整合Redis乱码原因及解决方案
问题描述:springboot使用springdataredis存储数据时乱码rediskey/value出现\\xAC\\xED\\x00\\x05t\\x00\\x05问题分析:查看RedisTemplate类!(https://oscimg.oschina.net/oscnet/0a85565fa
Stella981 Stella981
3年前
LeetCode 生命游戏,不用新数组的方式
原文链接: LeetCode生命游戏,不用新数组的方式(https://my.oschina.net/ahaoboy/blog/4958278)https://leetcodecn.com/problems/gameoflife/(https://www.oschina.net/action/GoToLink?urlhttps%3A%2
Stella981 Stella981
3年前
HashMap 的底层实现原理
HashMap是一个用于存储KeyValue键值对的集合,每一个键值对也叫做Entry。这些个Entry分散存储在一个数组当中,这个数组就是HashMap的主干。HashMap数组每一个元素的初始值都是Null。 !(https://oscimg.oschina.net/oscnet/8495d30fe00a2865dd74088d2
Wesley13 Wesley13
3年前
ES6 新增的数组的方法
给定一个数组letlist\//wu:武力zhi:智力{id:1,name:'张飞',wu:97,zhi:10},{id:2,name:'诸葛亮',wu:55,zhi:99},{id:3,name:'赵云',wu:97,zhi:66},{id:4,na
Wesley13 Wesley13
3年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
达里尔 达里尔
1年前
给数组添加新数据,判断数据是否重复
多选要进行数组拼接,希望判断往原数组里添的新数据是否重复,封装个简易方法languageconstdataArrayname:'aaa',id:1,name:'bbb',id:2;constnewDataname:'ccc',id:2;//要添加的新数
美凌格栋栋酱 美凌格栋栋酱
5个月前
Oracle 分组与拼接字符串同时使用
SELECTT.,ROWNUMIDFROM(SELECTT.EMPLID,T.NAME,T.BU,T.REALDEPART,T.FORMATDATE,SUM(T.S0)S0,MAX(UPDATETIME)CREATETIME,LISTAGG(TOCHAR(