【重点】【DP】152.乘积最大的子数组

2023-12-20 14:39:35

题目

法1:DP

参考:https://blog.csdn.net/Innocence02/article/details/128326633
f[i]表示以i结尾的连续子数组的最大乘积,d[i]表示以i结尾的连续子数组的最小乘积 。
如果只有正数,我们只需要考虑最大乘积f[i];有负数,需要考虑与负数相乘的数,越小越好。所以d[i] 维护最小乘积。
在这里插入图片描述

class Solution {
    public int maxProduct(int[] nums) {
        int max = nums[0], min = nums[0], res = nums[0];
        for (int i = 1; i < nums.length; ++i) {
            int tmpMax = max, tmpMin = min;
            max = Math.max(nums[i], Math.max(tmpMax * nums[i], tmpMin * nums[i]));
            min = Math.min(nums[i], Math.min(tmpMax * nums[i], tmpMin * nums[i]));
            res = Math.max(max, res);
        }

        return res;
    }
}

文章来源:https://blog.csdn.net/Allenlzcoder/article/details/135104859
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。