当前位置： 移动技术网 > IT编程>脚本编程>Ajax > [LeetCode] 动态规划题总结

[LeetCode] 动态规划题总结

2020年07月14日  | 移动技术网IT编程  | 我要评论

写在前面

动态规划在互联网公司的笔试题中经常会使大题的压轴题，解动态规划题的关键是定义动态规划变量和写出状态转移方程，本篇博客主要探讨动态规划题型解法，最后也会介绍动态规划与其他算法知识结合的题。

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

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网