当前位置:网站首页>【动态规划】连续子数组的最大和
【动态规划】连续子数组的最大和
2022-07-31 03:06:00 【#小苏打】
动态规划(DP):动态规划中每一个状态一定是由上一个状态推导出来的,有别于贪心,贪心是没有状态推导,而是从局部中选择最优的。
动态规划解题步骤
1:确定dp数组,dp[ i ]为包括下标 i 之前的最大连续子序列和。
2:确定状态转移方程,dp[ i ]有两个方向推出,dp[ i-1 ]+nums[ i ] 为加入当前连续子序列和,
num[ i ]为从头开始计算到下标为 i 的子序列和。
3:初始化dp数组,本题目可以看出dp[ i ]依赖于dp[ i-1 ],所以dp[ 0 ]是递推公司基础。
4:确定遍历顺序,本题需要从前往后遍历。
class Solution {
public int maxSubArray(int[] nums) {
int[] dp = new int[nums.length];
dp[0] = nums[0]; //初始化dp
int max = dp[0]; //作为一个中间变量输出最大值
for(int i = 1;i<nums.length;i++){
dp[i] = Math.max(dp[i-1]+nums[i],nums[i]); //状态转移方程
max = Math.max(max,dp[i]);
}
return max;
}
}
边栏推荐
- 编译Hudi
- CloudCompare & PCL calculate the degree of overlap between two point clouds
- 【C语言】三子棋(经典解法+一览图)
- C#远程调试
- [C language foundation] Solve C language error: expected ';', ',' or ')' before '&' token
- Problems that need to be solved in distributed system architecture
- 【C语言】表达式求值的一般方法
- MultipartFile文件上传
- The whole process scheduling, MySQL and Sqoop
- 想从手工测试转岗自动化测试,需要学习哪些技能?
猜你喜欢
Addition and Subtraction of Scores in LeetCode Medium Questions
刚出道“一战成名”,安全、舒适一个不落
递归查询单表-单表树结构-(自用)
MP使用时的几个常见报错
StringJoiner in detail
什么是分布式锁?实现分布式锁的三种方式
10 Permission introduction
品牌广告投放平台的中台化应用与实践
JS function this context runtime syntax parentheses array IIFE timer delay self.backup context call apply
Mysql 45讲学习笔记(二十三)MYSQL怎么保证数据不丢
随机推荐
LeetCode简单题之找到和最大的长度为 K 的子序列
Discourse Custom Header Links
Is interprofessional examination difficult?Low success rate of "going ashore"?Please accept this practical guide!
C# remote debugging
JetPack组件Databinding
C#远程调试
Annotation usage meaning
Problems that need to be solved in distributed system architecture
LeetCode中等题之分数加减运算
想从手工测试转岗自动化测试,需要学习哪些技能?
IDEA 注释报红解决
mycat的主从关系 垂直分库 水平分表 以及mycat分片联表查询的配置详解(mysql5.7系列)
The simulation application of common mode inductance is here, full of dry goods for everyone
10. Redis implements likes (Set) and obtains the total number of likes
局域网电脑硬件信息收集工具
下载jar包的好地方
【HCIP】ISIS
StringJoiner in detail
解析小结—自用
Moxa NPort device flaw could expose critical infrastructure to devastating attack