【LeetCode热题100】【动态规划】乘积最大子数组

叶茂林

发布于 2024-04-20 11:05:59

520

发布于 2024-04-20 11:05:59

文章被收录于专栏：叶子的开发者社区叶子的开发者社区

题目链接：152. 乘积最大子数组 - 力扣（LeetCode）

要找乘积最大的连续子数组，我们之前做过找和最大的连续子数组【LeetCode热题100】【普通数组】最大子数组和-CSDN博客

对于和来讲，定义dp[i]是以nums[i]为结尾的最大子数组的和，那么dp[i]要么就是nums[i]加上之前的dp[i-1]，即前一个子数组加上当前元素，要么是nums[i]自己新开一个子数组，所以状态转移方程

dp[i] = std::max(dp[i - 1] + nums[i], nums[i]);

但是乘积与和不一样的地方在于负数的情况，负数加负数的和是越来越小的，但是乘积会因为碰到一个负数变成最大或者变成最小，因此需要用两个数组记录状态，dpMin记录最小，dpMax记录最大

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

本文参与?腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2024-04-19，如有侵权请联系 cloudcommunity@tencent.com 删除