当前位置:网站首页>【动态规划】连续子数组的最大和
【动态规划】连续子数组的最大和
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;
}
}
边栏推荐
- 7年经验,功能测试工程师该如何一步步提升自己的能力呢?
- Local area network computer hardware information collection tool
- 10. Redis implements likes (Set) and obtains the total number of likes
- 工程(五)——小目标检测tph-yolov5
- Uninstallation of mysql5.7.37 under CentOS7 [perfect solution]
- SQL注入 Less47(报错注入) 和Less49(时间盲注)
- Discussion on Service Commitment of Class Objects under Multithreading
- IIR滤波器和FIR滤波器
- The simulation application of common mode inductance is here, full of dry goods for everyone
- MultipartFile file upload
猜你喜欢
CorelDRAW2022 streamlined Asia Pacific new features in detail
4. Sensitive word filtering (prefix tree)
SQL injection Less46 (injection after order by + rand() Boolean blind injection)
10. Redis implements likes (Set) and obtains the total number of likes
字体压缩神器font-spider的使用
CentOS7下mysql5.7.37的安装【完美方案】
MultipartFile文件上传
[Compilation principle] Lexical analysis program design principle and implementation
自动化办公案例:如何自动生成期数据?
TCP详解(一)
随机推荐
10 Permission introduction
学习DAVID数据库(1)
【shell基础】判断目录是否为空
【Android】Room —— SQLite的替代品
WebSocket Session is null
7、私信列表
Map.Entry理解和应用
StringJoiner in detail
LeetCode简单题之找到和最大的长度为 K 的子序列
JS 函数 this上下文 运行时点语法 圆括号 数组 IIFE 定时器 延时器 self.备份上下文 call apply
6. Display comments and replies
如何搭建私有yum源
TCP详解(三)
【C语言】表达式求值的一般方法
接口测试关键技术
Analysis summary - self-use
SQL 面试用题(重点)
【Cocos Creator 3.5】缓动系统停止所有动画
return in try-catch
观察者模式