CS-Wiki CS-Wiki
Home
知识体系总览
  • 数据结构与算法
  • 计算机网络
  • 操作系统
  • MySQL
  • Redis
  • 设计模式
  • Java 基础
  • Java 集合
  • Java 并发
  • Java 虚拟机
  • Spring
  • Kafka
  • 校招扫盲
  • 项目推荐
  • 唠唠嗑儿
  • 读书笔记
归档
GitHub (opens new window)
Home
知识体系总览
  • 数据结构与算法
  • 计算机网络
  • 操作系统
  • MySQL
  • Redis
  • 设计模式
  • Java 基础
  • Java 集合
  • Java 并发
  • Java 虚拟机
  • Spring
  • Kafka
  • 校招扫盲
  • 项目推荐
  • 唠唠嗑儿
  • 读书笔记
归档
GitHub (opens new window)
  • 刷题模板汇总
  • 一些刷题小技巧
  • 整数 and 位运算

  • 数组

  • 链表

  • 哈希表

  • 字符串

  • 栈

  • 队列

  • 二叉树

  • 前缀树

  • 二分查找

  • 双指针法

  • 区间求和问题

  • 排序

  • 回溯算法

  • 贪心算法

  • 动态规划

    • 动态规划理论基础
    • Fibonacci 问题

    • 背包问题

    • 打家劫舍问题

    • 买卖股票问题

    • 子串和子序列问题

      • 最长斐波那契数列
      • 摆动序列
      • 最长递增子序列
      • 最长连续递增序列
      • 最大子数组和
      • 最大子数组乘积
        • 📃 题目描述
        • 🔔 解题思路
        • 💥 复杂度分析
      • 最长重复子数组
      • 最长公共子序列
      • 不相交的线
      • 字符串交织
      • 判断子序列
      • 子序列的数目
      • 两个字符串的删除操作
      • 编辑距离
      • 最长回文子串
      • 最长回文子序列
      • 最少回文分割
      • 数组中的最长山脉
    • 矩阵路径问题

    • 其他

  • 图

  • 数学

  • 自动机

  • 海量数据和空间限制

  • 05-数据结构与算法
  • 动态规划
  • 子串和子序列问题
小牛肉
2022-09-22
目录

最大子数组乘积

# 📃 题目描述

题目链接:152. 乘积最大子数组 (opens new window)

# 🔔 解题思路

按照 53. 最大子数组和 - 力扣(LeetCode) (leetcode-cn.com) (opens new window) 这题的思路去做的话,即 dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]),这样会出现问题!

class Solution {
    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
		
        // nums[i] 左边的最大乘积
        int[] maxDp = new int[nums.length];
        // nums[i] 左边的最小乘积
        int[] minDp = new int[nums.length];

        // base case
        maxDp[0] = nums[0];
        minDp[0] = nums[0];

        int res = maxDp[0];

        for (int i = 1; i < nums.length; i ++) {
            maxDp[i] = Math.max(Math.max(maxDp[i - 1] * nums[i], minDp[i - 1] * nums[i]), nums[i]);
            minDp[i] = Math.min(Math.min(maxDp[i - 1] * nums[i], minDp[i - 1] * nums[i]), nums[i]);
            res = Math.max(maxDp[i], res);
        }

        return res;
    }
}

状态压缩:

class Solution {
    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
		
        // nums[i] 左边的最大乘积
        int preMax = nums[0];
        // nums[i] 左边的最小乘积
        int preMin = nums[0];

        int res = nums[0];

        for (int i = 1; i < nums.length; i ++) {
            int curMax = Math.max(Math.max(preMax * nums[i], preMin * nums[i]), nums[i]);
            int curMin = Math.min(Math.min(preMax * nums[i], preMin * nums[i]), nums[i]);

            res = Math.max(res, curMax);
            
            preMax = curMax;
            preMin = curMin;
        }

        return res;
    }
}

# 💥 复杂度分析

  • 空间复杂度:
  • 时间复杂度:

🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~

帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10
最大子数组和
最长重复子数组

← 最大子数组和 最长重复子数组→

最近更新
01
02
线上环境 CPU 使用率飙升如何快速排查?
03-05
03
面试官再跟你说中国没有根服务器,雪人计划让他了解下
02-23
更多文章>
Theme by Vdoing | Copyright © 2019-2023 飞天小牛肉 | 皖ICP备2022008966号
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式