[LeetCode] 动态规划题总结
程序员文章站
2022-06-25 12:12:36
写在前面动态规划在互联网公司的笔试题中经常会使大题的压轴题,解动态规划题的关键是定义动态规划变量和写出状态转移方程,本篇博客主要探讨动态规划题型解法,最后也会介绍动态规划与其他算法知识结合的题。152. 乘积最大子数组......
写在前面
动态规划在互联网公司的笔试题中经常会使大题的压轴题,解动态规划题的关键是定义动态规划变量和写出状态转移方程,本篇博客主要探讨动态规划题型解法,最后也会介绍动态规划与其他算法知识结合的题。
152. 乘积最大子数组
给你一个整数数组 nums ,请你找出数组中乘积最大的连续子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。
解题思路: 此题很容易受连续子数组最大和值 题的影响,以当前元素结尾序列的最大和值只取决于当前值、当前值+前一序列最大和,但是对于乘法,因为一个数a乘上数b,若数a是最大值,乘上数b后,若数b为正数,那么依然能保证是最大值,但是若数b为负数,反而会成为最小值,因此,我们会发现求当前位置的最大乘积值,要同时关心前一个位置的最大乘积值和最小乘积值,此题属于双动态规划题,定义动态规划变量mx[i]
表示以nums[i]
为结尾的最大乘积值,mn[i]
表示以nums[i]
为结尾的最小乘积值,状态转移方程如下:
mn[i] = min(nums[i], min(mn[i - 1] * nums[i], mx[i - 1] * nums[i]));
mx[i] = max(nums[i], max(mn[i - 1] * nums[i], mx[i - 1] * nums[i]));
// DP,以nums[i]为结尾的序列最大乘积由nums[i],MIN[i-1]*nums[i],MAX[i-1]*nums[i]
// 决定且取最大值,而最小乘积也有三者决定且取最小值
// T: O(n), space: O(n)
class Solution {
public:
int maxProduct(vector<int>& nums) {
int n = nums.size();
int res = nums[0];
vector<int> mn(n), mx(n);
mn[0] = nums[0];
mx[0] = nums[0];
for (int i = 1; i < n; ++i) {
mn[i] = min(nums[i], min(mn[i - 1] * nums[i], mx[i - 1] * nums[i]));
mx[i] = max(nums[i], max(mn[i - 1] * nums[i], mx[i - 1] * nums[i]));
res = max(res, mx[i]);
}
return res;
}
};
本文地址:https://blog.csdn.net/whutshiliu/article/details/107324717
上一篇: Python实现排序方法常见的四种
推荐阅读
-
动态规划算法题:机器人到达指定合位置方法数
-
[题记-动态规划] 编辑距离 - leetcode
-
动态规划详解(leetcode例题+解析)python
-
[Leetcode][第410题][JAVA][分割数组的最大值][动态规划][二分]
-
动态规划_leetcode.64.最小路径和
-
动态规划求解"疯狂的采药"问题(洛谷P1616题题解,Java语言描述)
-
【leetcode】121 买卖股票的最佳时机(动态规划)
-
动态规划---买卖股票的最佳时机(LeetCode 70)
-
LeetCode 买卖股票的最佳时机 (动态规划)
-
Longest Valid Parentheses leetcode java (求最长有效匹配括号子串的长度)-动态规划