152.乘积最大子数组

2020-10-14

算法 / 关联题目

字数统计: 1k | 阅读时长≈ 4 分钟

LeetCode

动态规划

确定状态

最后一步

只考虑最后一步，为，很好理解，就是最后一个元素，稍稍复杂一点

因为本题不是求和，较小的值在下一次计算后（加上一个数或减去一个数）仍然是较小的值，但是乘法收到正负符号的影响，一个负数乘以另一个负数，可以是一个正数，所以这个应该考虑正负的情况

子问题

由上面的分析，原问题为数组子数组城际的最大值，除去最后一步之后子问题为子数组的乘积最大值

所以用来表示子数组乘积最大值

转移方程

根据确定状态的分析，为上一步的最大值，考虑到正负符号的影响，应该同时保存最大值和最小值，因为最小值乘以可能变为最大值

初始条件和边界情况

初始化

用于记录最大值

计算顺序

， ，

 var maxProduct = function (nums) {
    var n = nums.length,
        // 初始化第一个
        // 考虑到f[1]依赖f[0]的结果至少要初始化一组数据
        f = [
            [nums[0], nums[0]]
        ],
        i = 1,
        res = nums[0];
    for (; i < n; i++) {
        if (f[i - 1][0] == 0) {
            f[i] = [nums[i], nums[i]]
        } else {
            var min = Math.min(f[i - 1][0] * nums[i], f[i - 1][1] * nums[i], nums[i]);
            var max = Math.max(f[i - 1][0] * nums[i], f[i - 1][1] * nums[i], nums[i]);
            f[i] = [min, max];
        }
        if (f[i][1] > res) res = f[i][1];
    }
    return res
};

优化

删除无用的代码

1
2
3

if (f[i - 1][0] == 0) {
    f[i] = [nums[i], nums[i]]
}

最初考虑到num[i+1]===0的情况，会将f[i+1]最小值，最大值都变为0，会使后面的循环计算都为0，但无需有这种担心，因为Math.min(f[i - 1][0] * nums[i], f[i - 1][1] * nums[i], nums[i]); 最大值最小值的计算都有nums[i]的比较，并不会使后面的运算一直为0

这里还需要考虑为什么需要用nums[i]，对于数组[-2,-3,0,2-2]

循环	值
初始化	f[0] = [-2,-2]，最大值最小值都为第一个数
1	f[1] = [6,-3]，有最小值并不是乘积得出的情况，而是元素本身就是最小值
2	f[2] = [0,0]，遇到零的情况
3	f[3] = [2,0]，最大值为元素本身，并不是乘积
4	f[4] = [0,-4]

var maxProduct = function (nums) {
    var n = nums.length,
        f = [
            [nums[0], nums[0]]
        ],
        i = 1,
        res = nums[0];
    for (; i < n; i++) {
            var min = Math.min(f[i - 1][0] * nums[i], f[i - 1][1] * nums[i], nums[i]);
            var max = Math.max(f[i - 1][0] * nums[i], f[i - 1][1] * nums[i], nums[i]);
            f[i] = [min, max];
        if (f[i][1] > res) res = f[i][1];
    }
    return res
};

优化数储存，可以发现我们每次存下来的最大值最小值，只会用在下一次的计算中，所以并不需要额外的空间把每一个结果保存下来，只需要三个变量

变量	作用
max	临时储存上一次的最大值
min	临时储存上一次的最小值
res	保存最终结果的最大值

var maxProduct = function (nums) {
    var n = nums.length,
        max = nums[0],
        min = nums[0],
        i = 1,
        res = nums[0];
    for (; i < n; i++) {
        var _min = Math.min(min * nums[i], max * nums[i], nums[i]);
        var _max = Math.max(min * nums[i], max * nums[i], nums[i]);
        // 防止相互影响
        min = _min;
        max = _max;
        if (max > res) res = max;
    }
    return res
};

通过判断是否负数，交换两个元素

初始化时min=1,max=1,巧妙的从下表为0的位置遍历

var maxProduct = function (nums) {
    var n = nums.length,
        max = 1,
        min = 1,
        res=-Infinity;
    for (var i=0; i < n; i++) {
        if(nums[i]< 0){
            var temp = max;
            max = min;
            min = temp;
        }
        var min = Math.min(min* nums[i], nums[i]);
        var max = Math.max(max*nums[i], nums[i]);
        if (max > res) res = max;
    }
    return res
};

复杂度分析

时间复杂度：程序一次循环遍历了，故渐进时间复杂度为。
空间复杂度：优化后只使用常数个临时变量作为辅助空间，与无关，故渐进空间复杂度为

打赏

版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！