思路
状态定义：dp[i]表示以i结尾的最大子数组和
转移方程：
计算dp[i]时，dp[0]到dp[i-1]的值已经求出
由于是连续数组，故不存在将nums[i]逐个与dp[n]搭配求解的过程
换言之
dp[i]仅与dp[i-1]有关
考虑极端情况下
当dp[i-1]<0时，求得的结果更小，故应舍弃
因此状态转移方程为：dp[i] = nums[i] > 0 ? nums[i] + max(dp[i-1],0) : max(dp[i-1],0)
初始值：
由于仅依赖比i小的O(1)个子问题，故用一个变量pre初始为0
边界：
dp[i-1]是否小于0，如果是<0,则舍弃
dp[i]是否小于0，如果是，则舍弃
实现
目录[https://www.jianshu.com/p/85e18c21317a] 题目[https://lee...
目录[https://www.jianshu.com/p/85e18c21317a] 题号[https://lee...
目录[https://www.jianshu.com/p/85e18c21317a] 题号[https://lee...
目录[https://www.jianshu.com/p/85e18c21317a] 题号[https://lee...
算法导论，线性时间，最大子数组和。这个思想，必须先要理解清楚，而后才能 写代码 。参考资料，感谢作者。https:...
目录[https://www.jianshu.com/p/85e18c21317a] 题目[https://lee...
继续 算法导论 最大子数组问题，线性时间，这次把索引，也计算出来 思路和代码，抄袭 https://www.cn...
最大子序列和最长公共子序列最长公共子串大整数相乘/除/加数组最大乘积
求最大子数组，最大子乘积
线性结构 数组、 单链表和双链表 数组和链表区别： 数组：数组元素在内存上连续存放，可以通过下标查找元素；插入、删...
本文标题：DP--最大子数组和（线性-单串）
本文链接：https://www.haomeiwen.com/subject/esdmkrtx.html
网友评论