LeetCode 152 Maximum Product Subarray

Tag: 动态规划法 LeetCode Posted on 2022-03-04 22:42:26 Edited on 2022-03-04 22:42:26 Views: 144

概述

https://leetcode.com/problems/maximum-product-subarray/

动态规划法

等等,子问题的最优解未必可用啊,我感觉我们应当存两个,一个最大的,一个最小的。

我去,AC 了,哈哈哈哈哈

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        auto maxdp = nums;
        auto mindp = nums;
        int ans = nums.back();
        for (int i = nums.size() - 2; i >= 0; i --) {
            maxdp[i] = max(nums[i], max(nums[i] * maxdp[i+1], nums[i] * mindp[i+1]));
            mindp[i] = min(nums[i], min(nums[i] * maxdp[i+1], nums[i] * mindp[i+1]));
            ans = max(ans, maxdp[i]);
        }
        return ans;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/