下载APP
登录
关闭
讲堂
算法训练营
Python 进阶训练营
企业服务
极客商城
客户端下载
兑换中心
渠道合作
推荐作者
当前播放: 47 | 面试题:乘积最大子序列
00:00 / 00:00
标清
  • 标清
1.0x
  • 2.0x
  • 1.5x
  • 1.25x
  • 1.0x
  • 0.5x
网页全屏
全屏
00:00
付费课程,可试看

算法面试通关40讲

共62讲 · 62课时·约600分钟
18804
免费
01 | 合格程序员的第一步:算法...
免费
02 | 如何事半功倍地学习算法与...
免费
03 | 如何计算算法的复杂度
免费
04 | 如何通过LeetCode来进行算...
免费
05 | 理论讲解:数组&链表
06 | 面试题:反转一个单链表&...
07 | 理论讲解:堆栈&队列
08 | 面试题:判断括号字符串是...
09 | 面试题:用队列实现栈&用...
10 | 理论讲解:优先队列
11 | 面试题:返回数据流中的第...
12 | 面试题:返回滑动窗口中的...
13 | 理论讲解:哈希表
14 | 面试题:有效的字母异位词
15 | 面试题:两数之和
16 | 面试题:三数之和
17 | 理论讲解:树&二叉树&二...
18 | 面试题:验证二叉搜索树
19 | 面试题:二叉树&二叉搜索...
20 | 理论讲解:二叉树遍历
21 | 理论讲解:递归&分治
22 | 面试题:Pow(x,n)
23 | 面试题:求众数
24 | 理论讲解:贪心算法
25 | 面试题:买卖股票的最佳时...
26 | 理论讲解:广度优先搜索
27 | 理论讲解:深度优先搜索
28 | 面试题:二叉树层次遍历
29 | 面试题:二叉树的最大和最...
30 | 面试题:生成有效括号组合
31 | 理论讲解:剪枝
32 | 面试题:N皇后问题
33 | 面试题:数独问题
34 | 理论讲解:二分查找
35 | 面试题:实现一个求解平方...
36 | 理论讲解:字典树
37 | 面试题:实现一个字典树
38 | 面试题:二维网格中的单词...
39 | 理论讲解:位运算
40 | 面试题:统计位1的个数
41 | 面试题:2的幂次方问题&...
42 | 面试题:N皇后问题的另一...
43 | 理论理解:动态规划(上)
44 | 理论理解:动态规划(下)
45 | 面试题:爬楼梯
46 | 面试题:三角形的最小路径...
47 | 面试题:乘积最大子序列
48 | 面试题:股票买卖系列
49 | 面试题:最长上升子序列
50 | 面试题:零钱兑换
51 | 面试题:编辑距离
52 | 理论讲解:并查集
53 | 面试题:岛屿的个数&朋友...
54 | 面试题:岛屿的个数&朋友...
55 | 理论讲解: LRU Cache
56 | 面试题:设计和实现一个LR...
57 | 理论讲解:布隆过滤器
58 | 课程重点回顾
59 | FAQ答疑&面试中切题四件...
60 | 回到起点:斐波拉契数列
61 | 白板实战番外篇:斐波拉契...
62 | 最后的一些经验分享

精选留言(22)

  • 2019-01-12
    还需要和自身a[i] 比较,这个白板没讲到
    8
  • 2019-01-23
     暴力写法写不出来~
    4
  • 2019-01-09
    如果是不连续的情况,只考虑正数的话会不会错过负负得正的情况?

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

    4
  • 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
  • 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
  • 2019-05-26
    这里dp[i]表示的并不是子问题的解,max(dp[i], dp[i-1], dp[i-2]...dp[0])才是。
    1
  • 2019-05-10
    暴力dfs写不出来,因为递归各层不知道是否连续。请指正。
    1
  • 2018-12-22
    DP 果然高深莫测啊。这题自己想真想不到...
    1
  • 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
    暴力 递归的有没有会的,写一个参考下?
  • 2019-08-04
    老师可以解释一下这种方法遇到零是怎么解决的吗?这一块有一点想不通

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

  • 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
    老师,这题本身思路就比较复杂,能不能在讲完思路实现后,再进行代码优化,这样更加有层次。
  • 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了。
  • 2019-03-27
    不需要一位数组了,只存上一个的最大值最小值就可以了