此专栏文章是对力扣上算法题目各种方法的总结和归纳, 整理出最重要的思路和知识重点并以思维导图形式呈现, 当然也会加上我对导图的详解.
目的是为了更方便快捷的记忆和回忆算法重点(不用每次都重复看题解), 毕竟算法不是做了一遍就能完全记住的. 所以本文适合已经知道解题思路和方法, 想进一步加强理解和记忆的朋友, 并不适合第一次接触此题的朋友(可以根据题号先去力扣看看官方题解, 然后再看本文内容).
关于本专栏所有题目的目录链接, 刷算法题目的顺序/注意点/技巧, 以及思维导图源文件问题请点击此链接.
想进大厂, 刷算法是必不可少的, 欢迎和博主一起打卡刷力扣算法, 博主同步更新了算法视频讲解 和 其他文章/导图讲解, 更易于理解, 欢迎来看!
文章目录
- 0.导图整理
- 1.与 最大子序和 的不同
- 2.优化空间
- 源码
- Python:
- java:
题目链接:https://leetcode-cn.com/problems/maximum-product-subarray/solution/si-wei-dao-tu-zheng-li-zui-da-zi-xu-ji-h-r8du/
0.导图整理
1.与 最大子序和 的不同
本题在思想上和 最大子序和 是非常相似的, 甚至连定义dp数组及下标的含义都是相同的: 用fmax(i)来表示以第 i 个元素结尾的乘积最大子数组的乘积, ai表示输入参数 nums.
但是如果直接根据经验写出这样的状态转移方程: fmax(i)=max{f(i−1)+ai,ai}是错误的, 用比较专业的语言解释就是: 这里的定义并不满足「最优子结构」, 当前位置的最优解未必是由前一个位置的最优解转移得到的. 用白话来解释就是: 两个负数相乘有可能会得到更大的结果, 当前的最大值并不一定是通过上个状态的最大值决定的, 也可能是上个状态的最小值决定的. 这都是因为加法和乘法的不同性质决定的.
通过这样的分析就决定了我们还必须同时维护上个状态的最小值, 然后就可以写出如下的状态转移方程了:
它代表第i个元素结尾的乘积最大子数组的乘积fmax(i), 可以考虑把ai加入第 i−1 个元素结尾的乘积最大或最小的子数组的乘积中, 二者加上ai, 三者取大, 就是第i个元素结尾的乘积最大子数组的乘积. 第i个元素结尾的乘积最小子数组的乘积fmin(i)同理.
这是两者思想上的不同, 在实现代码上, 也有着一点差别, 在没有进行空间优化之前, 我们是需要维护两个dp数组的, 而且这两个数组是完全独立的, 这就说明我们不能通过数组的引用这种浅拷贝的方式来操作数组, 必须将数组进行真实的复制(深拷贝)之后再进行相关的操作, 这就是如下代码的含义:
System.araycopy(nums, 0, maxF, 0, length);//nums从0开始的位置复制到maxF从0开始的位置,长度length
System.araycopy(nums, 0, minF, 0, length);//对数组进行深拷贝,不能简单的使用数组的引用(浅拷贝)
2.优化空间
当然本题是可以像 最大子序和 一样进行空间优化的, 上面讲述的深拷贝的思想, 是为了让大家有这种意识, 在不能进行空间优化的时候该如何进行处理.
本题的优化也是挺简单的, 只需要用两个变量来维护i−1时刻的两种状态即可.
这里有个Python和java语言的注意点: java中的max/min函数只能包含两个参数, 当含有有个变量时, 要先进行两两比较, 再将比较之后的结果和其他变量再比较, 而Python中的可以包含任意个参数, 直接一起比较即可.
源码
Python:
# 优化空间
class Solution:
def maxProduct(self, nums: List[int]) -> int:
maxF, minF, ans = nums[0], nums[0], nums[0]
length = len(nums)
for i in range(1, length):
mx, mn = maxF, minF # 只用两个变量来维护i−1时刻的状态,优化空间
maxF = max(mx * nums[i], nums[i], mn * nums[i])
minF = min(mn * nums[i], nums[i], mx * nums[i])
ans = max(maxF, ans)
return ans
java:
// 未优化空间
class Solution {
public int maxProduct(int[] nums) {
int length = nums.length;
int[] maxF = new int[length];
int[] minF = new int[length];//以第i个元素结尾的乘积最小子数组的乘积
System.araycopy(nums, 0, maxF, 0, length);//nums从0开始的位置复制到maxF从0开始的位置,长度length
System.araycopy(nums, 0, minF, 0, length);//对数组进行深拷贝,不能简单的使用数组的引用(浅拷贝)
for (int i = 1; i < length; ++i) {
//两个状态转移方程
maxF[i] = Math.max(maxF[i - 1] * nums[i], Math.max(nums[i], minF[i - 1] * nums[i]));
minF[i] = Math.min(minF[i - 1] * nums[i], Math.min(nums[i], maxF[i - 1] * nums[i]));
}
int ans = maxF[0];
for (int i = 1; i < length; ++i) {
ans = Math.max(ans, maxF[i]);
}
return ans;
}
}
// 优化空间
class Solution {
public int maxProduct(int[] nums) {
int maxF = nums[0], minF = nums[0], ans = nums[0];
int length = nums.length;
for (int i = 1; i < length; ++i) {
int mx = maxF, mn = minF;//只用两个变量来维护i−1时刻的状态,优化空间
maxF = Math.max(mx * nums[i], Math.max(nums[i], mn * nums[i]));
minF = Math.min(mn * nums[i], Math.min(nums[i], mx * nums[i]));
ans = Math.max(maxF, ans);
}
return ans;
}
}
我的更多精彩文章链接, 欢迎查看
各种电脑/软件/生活/音乐/动漫/电影技巧汇总(你肯定能够找到你需要的使用技巧)
力扣算法刷题 根据思维导图整理笔记快速记忆算法重点内容(欢迎和博主一起打卡刷题哦)
计算机专业知识 思维导图整理
最值得收藏的 Python 全部知识点思维导图整理, 附带常用代码/方法/库/数据结构/常见错误/经典思想(持续更新中)
最值得收藏的 C++ 全部知识点思维导图整理(清华大学郑莉版), 东南大学软件工程初试906科目
最值得收藏的 计算机网络 全部知识点思维导图整理(王道考研), 附带经典5层结构中英对照和框架简介
最值得收藏的 算法分析与设计 全部知识点思维导图整理(北大慕课课程)
最值得收藏的 数据结构 全部知识点思维导图整理(王道考研), 附带经典题型整理
最值得收藏的 人工智能导论 全部知识点思维导图整理(王万良慕课课程)
最值得收藏的 数值分析 全部知识点思维导图整理(东北大学慕课课程)
最值得收藏的 数字图像处理 全部知识点思维导图整理(武汉大学慕课课程)
红黑树 一张导图解决红黑树全部插入和删除问题 包含详细操作原理 情况对比
各种常见排序算法的时间/空间复杂度 是否稳定 算法选取的情况 改进 思维导图整理
人工智能课件 算法分析课件 Python课件 数值分析课件 机器学习课件 图像处理课件
考研相关科目 知识点 思维导图整理
考研经验–东南大学软件学院软件工程(这些基础课和专业课的各种坑和复习技巧你应该知道)
东南大学 软件工程 906 数据结构 C++ 历年真题 思维导图整理
东南大学 软件工程 复试3门科目历年真题 思维导图整理
最值得收藏的 考研高等数学 全部知识点思维导图整理(张宇, 汤家凤), 附做题技巧/易错点/知识点整理
最值得收藏的 考研线性代数 全部知识点思维导图整理(张宇, 汤家凤), 附带惯用思维/做题技巧/易错点整理
高等数学 中值定理 一张思维导图解决中值定理所有题型
考研思修 知识点 做题技巧 同类比较 重要会议 1800易错题 思维导图整理
考研近代史 知识点 做题技巧 同类比较 重要会议 1800易错题 思维导图整理
考研马原 知识点 做题技巧 同类比较 重要会议 1800易错题 思维导图整理
考研数学课程笔记 考研英语课程笔记 考研英语单词词根词缀记忆 考研政治课程笔记
Python相关技术 知识点 思维导图整理
Numpy常见用法全部OneNote笔记 全部笔记思维导图整理
Pandas常见用法全部OneNote笔记 全部笔记思维导图整理
Matplotlib常见用法全部OneNote笔记 全部笔记思维导图整理
PyTorch常见用法全部OneNote笔记 全部笔记思维导图整理
Scikit-Learn常见用法全部OneNote笔记 全部笔记思维导图整理
Java相关技术/ssm框架全部笔记
Spring springmvc Mybatis jsp
科技相关 小米手机
小米 红米 历代手机型号大全 发布时间 发布价格
常见手机品牌的各种系列划分及其特点
历代CPU和GPU的性能情况和常见后缀的含义 思维导图整理