【每日一题】- 2019-08-22 - 子数组的最大乘积

[azl397985856]

给定一个长度为N的整数数组，只允许乘法，不能用除法。计算任意 N - 1 个数的组合中乘积最大的一组，并写出算法的时间复杂度。

[xiongcaihu]

/**
 * 动态规划，设dp[i]为以第i个元素结尾的最大乘积，
 * 它可能是和dp[j..0]（j<i）的最大值或者最小值或者只有它自己构成最大乘积
 * 
 * 所以每次需要dp[i]里记录最大值和最小值
 * 
 * dp[i].max = max(nums[i],nums[i]*dp[i-1..0].max,nums[i]*dp[i-1..0].min)
 * dp[i].min = min(nums[i],nums[i]*dp[i-1..0].max,nums[i]*dp[i-1..0].min)
 *
 * 最后取dp[0..i]中max属性的最大值
 * 
 * 复杂度 O(n^2)
 * 
 * @param {*} nums
 * @returns
 */
function maxProduct(nums) {
    if (nums.length == 0) return 0;
    var dp = new Array(nums.length);
    dp[0] = {
        max: nums[0],
        min: nums[0]
    }
    var finalMax = nums[0];
    for (var i = 1; i < nums.length; i++) {
        dp[i] = {
            max: nums[i],
            min: nums[i]
        }
        for (var j = i - 1; j >= 0; j--) {
            var a = nums[i] * dp[j].max;
            var b = nums[i] * dp[j].min;
            dp[i].max = Math.max(dp[i].max, a, b);
            dp[i].min = Math.min(dp[i].min, a, b);
            finalMax = Math.max(finalMax, dp[i].max);
        }
    }
    return finalMax.toFixed(0);
}

[raof01]

// 动态规划设dp[i]为以第i个元素结尾的最大乘积，有dp[i]=Math.max(nums[i],nums[i]*dp[i-1]...nums[i]*dp[0]);
// 复杂度O(n^2)
var maxProduct = function (nums) {
    var dp = new Array(nums.length).fill(1);
    for (var i = 0; i < nums.length; i++) {
        dp[i] = nums[i];
        for (var j = i - 1; j >= 0; j--) {
            dp[i] = Math.max(dp[i], nums[i] * dp[j]);
        }
    }
    return Math.max(...dp);
}

这个状态迁移有问题，没有考虑出现负数应该截断，也没有考虑负负得正的情况：
[2,3,-2,4] => 6，[-1,1,2,3,-4] =>24，但你的代码算出来的结果正好相反。

[xiongcaihu]

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        auto maxEnd = nums[0], minEnd = nums[0], maxHere = nums[0], minHere = nums[0], ret = nums[0];
        for (auto i = 1; i < nums.size(); ++i) {
            auto tempMax = nums[i] * maxEnd;
            auto tempMin = nums[i] * minEnd;
            maxHere = max(nums[i], max(tempMin, tempMax));
            minHere = min(nums[i], min(tempMin, tempMax));
            maxEnd = maxHere;
            minEnd = minHere;
            ret = max(ret, maxHere);
        }
        return ret;
    }
};

你这个是求的连续子序列的最大乘积，它这题是求的不连续的，任意组合。

[raof01]

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        auto maxEnd = nums[0], minEnd = nums[0], maxHere = nums[0], minHere = nums[0], ret = nums[0];
        for (auto i = 1; i < nums.size(); ++i) {
            auto tempMax = nums[i] * maxEnd;
            auto tempMin = nums[i] * minEnd;
            maxHere = max(nums[i], max(tempMin, tempMax));
            minHere = min(nums[i], min(tempMin, tempMax));
            maxEnd = maxHere;
            minEnd = minHere;
            ret = max(ret, maxHere);
        }
        return ret;
    }
};

你这个是求的连续子序列的最大乘积，它这题是求的不连续的，任意组合。

嗯。。。删掉删掉

[xiongcaihu]

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        auto maxEnd = nums[0], minEnd = nums[0], maxHere = nums[0], minHere = nums[0], ret = nums[0];
        for (auto i = 1; i < nums.size(); ++i) {
            auto tempMax = nums[i] * maxEnd;
            auto tempMin = nums[i] * minEnd;
            maxHere = max(nums[i], max(tempMin, tempMax));
            minHere = min(nums[i], min(tempMin, tempMax));
            maxEnd = maxHere;
            minEnd = minHere;
            ret = max(ret, maxHere);
        }
        return ret;
    }
};

你这个是求的连续子序列的最大乘积，它这题是求的不连续的，任意组合。

嗯。。。删掉删掉

这么优雅的代码，别删了，加句话就行：本题解对应https://leetcode-cn.com/problems/maximum-product-subarray/ 此题。 :)

[raof01]

仔细想了想，这道题不是动态规划。任意N-1个数的乘积，也就是说需要求出每个位置上除自己之外的所有数字的乘积——这也是题目里面说不能用除法的原因，然后取一个最大值。比如：对[2,3,-2,4]做除掉自己之外的乘积得到：[-24,-16,24,-12]，最大值24。

[azl397985856]

仔细想了想，这道题不是动态规划。任意N-1个数的乘积，也就是说需要求出每个位置上除自己之外的所有数字的乘积——这也是题目里面说不能用除法的原因，然后取一个最大值。比如：对[2,3,-2,4]做除掉自己之外的乘积得到：[-24,-16,24,-12]，最大值24。

嗯嗯。 直观的解法是N^2 ， 通过空间换时间，可以到N。 但是还有更多的方法

[azl397985856]

领取

[azl397985856]

子数组的最大乘积

暴力法

function LSP(list) {
  let ret = 1;
  let max = -Number.MAX_VALUE;
  for (let i = 0; i < list.length; i++) {
    for (let j = 0; j < list.length; j++) {
      if (i !== j) ret *= list[j];
    }
    max = Math.max(max, ret);
    ret = 1;
  }
  return max;
}

空间换时间

function LSP(list) {
  let ret = 1;
  let max = -Number.MAX_VALUE;
  const l = [];
  const r = [];
  l[0] = 1;
  r[0] = 1; // useless
  r[list.length] = 1;

  for (let i = 1; i < list.length; i++) {
    l[i] = l[i - 1] * list[i - 1];
  }
  for (let i = list.length - 1; i >= 1; i--) {
    r[i] = r[i + 1] * list[i];
  }
  for (let i = 0; i < list.length; i++) {
    ret *= l[i] * r[i + 1];
    max = Math.max(max, ret);
    ret = 1;
  }

  return max;
}

数学分析

function LSP(list) {
  let ret = 1;
  let smallestPositive = Number.MAX_VALUE;
  let smallestPositiveI = -1;
  let largestNegative = -Number.MAX_VALUE;
  let largestNegativeI = -1;
  let firstZeroI = -1;

  let missingI = -1;

  // 总体的乘积分三种情况
  // 正负0
  // 如果是0， 找有没有别的0，有的话返回0, 没有的话我们就算下除了这个0之外所有的乘积，然后取它和0的较大值即可。(然而这两个逻辑可以合并)
  // 如果是正，那么删除最小的正数即可
  // 如果是负数，则说明一定至少有一个负数存在，我们只要知道绝对值最小的负数删除即可
  let productAll = 1;

  for (let i = 0; i < list.length; i++) {
    productAll *= list[i];
    if (list[i] === 0 && firstZeroI === -1) {
      firstZeroI = i;
    }
    if (list[i] > 0 && list[i] < smallestPositive) {
      smallestPositive = list[i];
      smallestPositiveI = i;
    }
    if (list[i] < 0 && list[i] > largestNegative) {
      largestNegative = list[i];
      largestNegativeI = i;
    }
  }
  if (productAll > 0) {
    missingI = smallestPositiveI;
  } else if (productAll < 0) {
    missingI = largestNegativeI;
  } else {
    missingI = firstZeroI;
  }

  for (let i = 0; i < list.length; i++) {
    if (i !== missingI) ret *= list[i];
  }

  return firstZeroI === -1 ? ret : Math.max(0, ret);
}