精选留言(22)

• 
  雨轩剑

  2019-01-12

  还需要和自身a[i] 比较，这个白板没讲到

  

   8
• 
  观弈道人

  2019-01-23

   暴力写法写不出来~
  

  

   4
• 
  林衡

  2019-01-09

  如果是不连续的情况，只考虑正数的话会不会错过负负得正的情况？

  作者回复: 再附加把偶数个绝对值最大的负数也乘进来。

  

   4
• 
  DanielAnton

  2019-04-04

  暴力法参考@大可可的代码，希望可以指正，共同学习
      // 暴力法
      public static int maxProduct(int[] nums) {
          int max = Integer.MIN_VALUE;
          for(int i = 0; i < nums.length; i++) {
              for(int j = i; j < nums.length; j++) {
                  int[] subNums = Arrays.copyOfRange(nums, i, j + 1); // 复制的区间是左闭右开，即不包括j+1
                  int product = 1;
                  for(int k = 0; k < subNums.length; k++) {
                      product *= subNums[k];
                  }
                  if(max < product)
                      max = product;
              }
          }
          return max;
      }
      // 动态规划
      public static int maxProduct2(int[] nums) {
          int[][] dp = new int[2][2]; // 第一维表示数组的长度，由于不需要保存整个数组，所以长度只需要取2即可，第二维用0表示是正的最大值，用1表示为负的最大值
          int res = nums[0]; // 最终的结果
          dp[0][0] = nums[0];
          dp[0][1] = nums[0];
          for(int i = 1; i < nums.length; i++) {
              int x = i % 2;
              int y = (i - 1) % 2; // 滚动数组，取值 0 or 1
  // if (nums[i] >= 0) {
  // dp[x][0] = Math.max(dp[y][0] * nums[i], nums[i]); // 正的最大值
  // dp[x][1] = Math.min(dp[y][1] * nums[i], nums[i]); // 负的最大值
  // } else {
  // dp[x][0] = Math.max(dp[y][1] * nums[i], nums[i]); // 正的最大值，负负得正
  // dp[x][1] = Math.min(dp[y][0] * nums[i], nums[i]); // 负的最大值
  // }
              // 上面的if语句可以简写成下面这样
              dp[x][0] = Math.max(Math.max(dp[y][0] * nums[i], dp[y][1] * nums[i]), nums[i]);
              dp[x][1] = Math.min(Math.min(dp[y][0] * nums[i], dp[y][1] * nums[i]), nums[i]);
              res = Math.max(res, dp[x][0]); // 最后的结果取决于正的最大值
          }
          return res;
      }

  展开

  作者回复: 酷！ 👍

  

   2
• 
  Js

  2019-09-30

  int maxProduct(vector<int>& nums) {
          int crtMax = INT_MIN;
  
          int size = nums.size();
  
          for (int i = 0; i != size; ++i) {
              int max = 1;
              for (int j = i; j != size; ++j) {
                  max *= nums[j];
  
                  if (max > crtMax) {
                      crtMax = max;
                  }
              }
          }
  
          return crtMax;
      }

  展开

  

   1
• 
  陈志恒

  2019-09-28

  1.这道题和前两道题对比：这里的递归方法（深度枚举）并不体现出递推方程，而前两道题即使在递归（回朔）中也可以看出递推方程。
  2.要有确定状态维度的概念：一维或多维。一般情况下，n维的数据，n维的状态，但这道题不是

  

   1
• 
  ssala

  2019-05-26

  这里dp[i]表示的并不是子问题的解，max(dp[i], dp[i-1], dp[i-2]...dp[0])才是。

  

   1
• 
  王磊

  2019-05-10

  暴力dfs写不出来，因为递归各层不知道是否连续。请指正。

  

   1
• 
  frogoscar

  2018-12-22

  DP 果然高深莫测啊。这题自己想真想不到...

  

   1
• 
  Aliliin

  2019-11-29

  PHP 的两种解法：
  
  // 看着厉害的版本
      function maxProduct1($nums)
      {
          if (empty($nums)) return 0;
          $maxNumber = PHP_INT_MIN; // （此PHP版本中支持的最小整数。）
          $max = 1;
          $min = 1;
          for ($i = 0; $i < count($nums); $i++) {
              if ($nums[$i] < 0) {
                  $temp = $max;
                  $max = $min;
                  $min = $temp;
              }
              $max = max($nums[$i], ($nums[$i] * $max));
              $min = min($nums[$i], ($nums[$i] * $min));
              $maxNumber = max($max, $maxNumber);
          }
          return $maxNumber;
      }
  
      // 动态规划版本
      function maxProduct($nums)
      {
          if (empty($nums)) return 0;
          $dp[0][0] = $dp[0][1] = $nums[0];
          // 最终的结果 PHP 如果不这样子定义结果会出现偏差
          $res = PHP_INT_MIN; // （此PHP版本中支持的最小整数。）
          for ($i = 0; $i < count($nums); $i++) {
              $x = $i % 2;
              $y = ($i - 1) % 2;
              $n = empty($dp[$y][0]) ? 1 : $dp[$y][0];
              $m = empty($dp[$y][1]) ? 1 : $dp[$y][1];
              $dp[$x][0] = max(max($n * $nums[$i], $m * $nums[$i]), $nums[$i]);
              $dp[$x][1] = min(min($n * $nums[$i], $m * $nums[$i]), $nums[$i]);
              $res = max($res, $dp[$x][0]);
          }
          return $res;
      }

  展开

  

  
• 
  邱

  2019-11-28

  写出了，暴力递归。使用二维数组做缓存，结果最后一条case，超出内存限制。
  private int recursion(int[] nums, int[][] mem, int start, int end) {
      if (start >= nums.length || end >= nums.length) {
          return 0;
      }
  
      if (mem[start][end] != 0) {
          return mem[start][end];
      }
  
      int result = nums[start];
      for (int i = start + 1; i <= end; i++) {
          result = nums[i] * result;
      }
      int row = recursion(nums, mem, start, end + 1);
      int col = recursion(nums, mem, start + 1, end);
      mem[start][end] = Math.max(row, Math.max(col, result));
      return mem[start][end];
  }
  
  public int maxProduct(int[] nums) {
      if (nums.length == 1) {
          return nums[0];
      }
      int[][] mem = new int[nums.length][nums.length];
      return recursion(nums, mem, 0, 0);
  }

  展开

  

  
• 
  邱

  2019-11-28

  暴力 递归的有没有会的，写一个参考下？

  

  
• 
  Claude Chen

  2019-08-04

  老师可以解释一下这种方法遇到零是怎么解决的吗？这一块有一点想不通

  作者回复: 遇到0就隔断；然后重新开始看后面的元素。

  

  
• 
  LeonTung

  2019-07-08

  写一个Golang版本的递归
  
  func maxProduct(nums []int) int {
      s := Solution{Nums: nums}
      return s.Run()
  }
  
  type Solution struct {
      Nums []int
      max int
  }
  
  func (s *Solution) Run() int {
      if len(s.Nums) > 0 {
          // init max val
          s.max = s.Nums[0]
      }
      s.helper(0)
      return s.max
  }
  
  func (s *Solution) helper(i int) {
      if i > len(s.Nums)-1 {
          return
      }
      product := 1
      for j := i; j < len(s.Nums); j++ {
          product *= s.Nums[j]
          if product > s.max {
              s.max = product
          }
      }
      s.helper(i + 1)
  }

  展开

  

  
• 
  克里斯

  2019-07-01

  原始版
  public int maxProduct(int[] nums) {
         if (nums == null || nums.length == 0) {
              return 0;
          }
          int[] max = new int[nums.length];
          int[] min = new int[nums.length];
          max[0] = nums[0];
          min[0] = nums[0];
          for (int i = 1; i < nums.length; i++) {
              if (nums[i] > 0) {
                  max[i] = Math.max(nums[i], nums[i] * max[i - 1]);
                  min[i] = Math.min(nums[i], nums[i] * min[i - 1]);
              } else {
                  max[i] = Math.max(nums[i], nums[i] * min[i - 1]);
                  min[i] = Math.min(nums[i], nums[i] * max[i - 1]);
              }
          }
          int imax = Integer.MIN_VALUE;
          for (int i = 0; i < nums.length; i++) {
              if (max[i] > imax) {
                  imax = max[i];
              }
          }
          return imax;
      }
  
  优化版
  public int maxProduct(int[] nums) {
         if (nums == null || nums.length == 0) {
              return 0;
          }
          int max = nums[0];
          int min = nums[0];
          int imax = nums[0];
          for (int i = 1; i < nums.length; i++) {
              if (nums[i] > 0) {
                  max = Math.max(nums[i], nums[i] * max);
                  min = Math.min(nums[i], nums[i] * min);
              } else {
                  int temp = Math.max(nums[i], nums[i] * min);
                  min = Math.min(nums[i], nums[i] * max);
                  max = temp;
              }
              imax = Math.max(imax, max);
          }
          return imax;
      }

  展开

  

  
• 
  克里斯

  2019-07-01

  老师，这题本身思路就比较复杂，能不能在讲完思路实现后，再进行代码优化，这样更加有层次。

  

  
• 
  Zu3zz

  2019-05-13

  视频中给出的第二种解法没有考虑到如果数组中含有0的情况 会出错

  作者回复: 零的情况在代码里可以处理一下

   1

  
• 
  王磊

  2019-05-10

  最终还是写了一个DFS版本 - 就是将递推转变为dfs的递归，每次带上最大和最小两个状态，当递归到数组末尾，返回。过程中，始终记录最大值。
  ···
  class Solution {
      int res = Integer.MIN_VALUE;
      public int maxProduct(int[] nums) {
          if (nums.length == 0) return 0;
          dfs(nums, 0, 1, 1);
          return res;
      }
  
      public void dfs(int[] nums, int i, int positive, int negative) {
          if (i == nums.length) return;
  
          int num = nums[i];
  
          if (num >= 0){
              positive = positive * num;
              negative = negative * num;
             if (num > positive) positive = num;
          }else {
              int negative1 = positive * num;
              positive = negative * num;
              negative = negative1;
              if (num < negative) negative = num;
          }
          if (res < positive) res = positive;
          dfs(nums, i + 1, positive, negative);
      }
  }
  ···

  展开

  作者回复: 👍👍

  

  
• 
  程运来

  2019-04-21

  我觉得这里老师的讲解考虑得不是很全面。应该要存两个数，分别是正数的最大值，和负数的最小值，而且还应该有一个标签来识别是不是存在正数和负数。比如，-1,2,3.到2时，正数最大值应该是2，但是按照老师讲的，正数最大值就是-2了。

  

  
• 
  billy

  2019-03-27

  不需要一位数组了，只存上一个的最大值最小值就可以了

  

  