Questions:

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example 1:

Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Example 2:

Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

Thinking:

  • Method1:
    • 考虑使用dp, 但是会超时
    • 2 3 -2 4
    • 0 6 -6 -8
    • 0 0 -12 -24
    • 0 0 0 -48
class Solution {
    public int maxProduct(int[] nums) {
        int len = nums.length;
        int[][] dp = new int[len][len];
        int result = Integer.MIN_VALUE;
        for(int i = 0; i < len; i++){
            dp[0][i] = nums[i];
            result = Math.max(result, nums[i]);
        }
        for(int i = 1; i < len; i++){
            for(int j = 1; j <= i; j++){
                dp[j][i] = dp[0][i] * dp[j - 1][i - 1];
                result = Math.max(result, dp[j][i]);
            }
        }
        return result;
    }
}
  • Method2:
    • 只需要记录上一层的最大值和最小值。就能将复杂度从O(N^2)降到O(n).
class Solution {
    public int maxProduct(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        int len = nums.length;
        int max = nums[0];
        int min = nums[0];
        int result = nums[0];
        for(int i = 1; i < len; i++){
            int temp = max;
            max = Math.max(nums[i], Math.max(max * nums[i], min * nums[i]));
            min = Math.min(nums[i], Math.min(temp * nums[i], min * nums[i]));
            result = Math.max(result, max);
        }
        return result;
    }
}

二刷

  1. 首先想到的还是最简单的dp，TLE。
  2. 参考一刷的结果。实际上当前的最大值可能分为两种情况：
    • 当前为正数，我们需要用上一位储存的最大值与之相乘。
    • 当前为负数，我们需要用上一位的最小值去乘。上一位的最小值不一定是要负数，乘以负数，想要获得最大值，另一个乘数只要越小越好。 
      class Solution {
 public int maxProduct(int[] nums) {
  int len = nums.length;
  int[][] dp = new int[len][len];
  int result = Integer.MIN_VALUE;
  for(int i = 0; i < len; i++){
      dp[0][i] = nums[i];
      result = Math.max(result, nums[i]);
  }
  for(int i = 1; i < len; i++){
      for(int j = 1; j <= i; j++){
          dp[j][i] = dp[0][i] * dp[j - 1][i - 1];
          result = Math.max(result, dp[j][i]);
      }
  }
  return result;
 }
}