本文主要是介绍算法题解记录30+++乘积最大子序列(百题筑基),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
我是蚊子码农,本次为大家带来一道经典的“动态规划”问题解题思路。
一、题目描述
给你一个整数数组 nums ,请你找出数组中乘积最大的非空连续
子数组
(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。
示例 1:
输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
提示:
1 <= nums.length <= 2 * 104
-10 <= nums[i] <= 10
nums 的任何子数组的乘积都 保证 是一个 32-位 整数
二、解题准备
过去,这一部分会从“题意”、“基础操作”、“基本原理”出发,进行讲解。
为了减少文章复杂性,默认读者理解题意【假设有易错的题目,我会讲解】、熟悉大部分通用数据结构的操作、了解常规题目的基本原理。
本部分,正式修改为,只描述一种朴素的、以遍历为主要方法的解决方案。
按本题为例,对于这道题,不难从遍历的角度出发。
第一,遍历的思路
我们要求最大的乘积子序列。
第一步,可以先从下标0开始,依次遍历数组【0】、【0,1】、【0,1,2】、……【0,1,……n-1】
得到其中最大的max,这时,max代表了以0开始的,最大的乘积子序列。
同理,迭代进行。
从下标1开始,依次遍历数组【1】、【1,2】……【1,2,……n-1】。
得到以1开始的、最大的乘积子序列。
接着是以下标2开始、3开始、……一直到n-1开始……
第二,遍历的正确性证明
AA.子序列组合的数目证明
第一,假设有一数组【0】,那么,其子序列只有【0】一个。(子序列,要求必须有元素)
第二,假设有数组【0,1】,那么,子序列有【0】【0,1】【1】3个。
第三,假设有数组【0,1,2】,那么有6个。
实际上,如果从末尾添加的元素的角度出发(比如第二里的“1”,第三里的“2”),该数组里的其它元素,都要和末尾元素作用,一共n-1个,另外,还要有末尾元素自身成子序列,所以一共新增n个。
举个例子,对于【0,1】数组,新增一个元素【2】,新生的数组【0,1,2】,比较原数组,增加了3个子序列
【0,1,2】, 【1,2】, 【2】。
证明子序列的增加规律后,我们列举数组长度,与子序列数目的关系。
当数组长度为1时,有1个子序列。
当数组长度为2时,有3个子序列。
当数组长度为3时,有6个子序列。
……
很容易得到,当数组长度为n时,有n * (n+1)/2个子序列。
AB.子序列遍历未重复、无空集、数目合规证明
这个非常好理解,由于每次遍历,元素开头的下标、结尾的下标都不同,容易得知。
比如数组【0,1,2】
按照遍历的顺序,
第一个以0开头,遍历到2结尾,也就是会遍历3个子序列。
【0】,【0,1】,【0,1,2】
第二个以1开头,遍历到2结尾
【1】,【1,2】
第三个以2开头
【2】
容易看到,不会产生空集、重复问题。
而且,数目也合理。【在此不再证明,本质和上面类似。】
AC.子序列遍历时,遍历的数据满足子序列结构证明
其实依照上面的例子,也能发现不会出错。
也就是说,结构满足。【不满足的情况不说了,不属于定义问题,而是实现问题】
第三, 遍历的缺点
遍历实现的代码,在力扣152题是可以过关的。
但是,时间复杂度很高,是O(n的平方),所以,答案只能超过3%的人。
其实大家估计也猜到了,既然使用了动态规划,必然会优化遍历最大的缺点–“重复计算过多”的问题。
举个例子,对于数组【0,1,2】
遍历时,以0下标开始,有3次计算
【0】,【0,1】,【0,1,2】
这里不存在重复,因为【0】*【1】得到子序列【0,1】的值。
【0,1】的值 乘以【2】得到【0,1,2】的值。
然而,到了以1下标开始时,有2次运算。
【1】,【1,2】
【0,1,2】的运算,本质包含了【1,2】的运算。
如果硬要说,其实把【1】的运算也包括了。
所以,遍历代码复杂度过高,不适合工程。
三、解题方案【动态规划】
这道题的动态规划,其实相当复杂,用起来一知半解。
为了解决问题,我们首先要用一些特例,来思考这道问题。
注意:这些数组不包含0。【实际问题会有,但是并不影响题目结构】
第一,全是正数的数组。
对于数组【2,3,4,7】
容易得到,最大乘积子序列,就是整个数组。
由于题目给定的数据,必然>=1,所以即使有1,也不影响整个数组的结果。
第二,全是负数的数组
容易发现,存在2种情况。
对于数组【-2,-1,-3】
可以得到,最大为序列【-1】,结果为-1。
对于数组【-2,-3】
最大序列为整个数组,结果是6。
我们发现,如果负数有偶数个,那么整个数组即为结果。
如果负数是奇数个,最大的数据即为结果。
第三,常规数组
假设有数组【2,-5,-2,-4,3】
(答案:24)
此时,我们发现以上面两种结构,无法解释这个答案。
定义:累积量
我们定义一种概念,用于理解这些数据。
累积量:即从下标i到j中,绝对值最大的数。
很明显,对于题目数组,累积量最大为原数组(因为没有0,且绝对值都大于等于1),即 -240
在一个数组中,从下标0出发,累积量一定越来越大。
所以,可以得到累积量数组为
【2, -10, 20, -80, -240】
常规角度理解
声明:这个思路是我忽然想到的,虽然是错的,但是也是我后来理解的基础。
既然累积量一定是随着数组越来越大的,那么,
假使数组下标为k时, Num【k】小于0,并且累积量小于0,则最大值为累积量 乘以 Num【k】。
假使数组下标为k时,Num【k】小于0,而累积量大于0,则最大值为Num【k】。
假使数组下标为k时,Num【k】大于0,而累积量大于0,那么最大值即 累积量*Num【k】
同理。
错误讲解
想必大家也容易发现我的谬误。
这个理论,没法解释数组【2,-5,-2,-4,3】
因为,其答案为【-2,-4,3】,结果是24。
而我的理论,结果为20,是以【2,-5,-2】组成的。
错误的原因:累积量事实上,忽略了其它情况,而是单纯以下标0开始。【或者说,以0的下一位数据】
第一步,情况思考
对于数组【2,-5,-2,-4,3】来说,
不存在负数时,容易知道,计算所有值,就是最大值。
出现第一个负数-5时,很容易知道,不选择-5,就是最大值。
出现第二个负数,可知,计算所有值,就是最大值。
……
容易发现。
奇数次的负数个数,要么选择前半段,要么选择后半段。【前半段:删除最后一个负数;后半段:删除第一个负数】
偶数次负数个数,直接选择全部数组即可。
最特殊的,就是奇数次负数个数,我们无法确定其值,从前往后运算一遍,又大大浪费时间。
思考这样的问题:我们能不能用一些变量,将前后在隐性中比较呢?
又或者,我们干脆用一些变量,把这些累积量、奇数次负数、偶数次负数表示出来?
第二步,翻转定义【困难】
这一步比较复杂。
理论上,我们可以定义以下标i开始的,最大的子序列。
那么,我们同样可以逆转定义,定义以下标i结尾的,最大的子序列。
我们设这个值为imax。
我们很容易得到这样的信息:
这里数组内的定义,是指从0开始,到下标i的子数组。
当数组内负数为偶数时,imax代表着全部数组累积量。【也就是说,从0开始,到下标i】
当数组内负数为奇数时,imax代表后半段累积量。【即,从第二个负数开始,到下标i】
但是,imax在实现上是非常困难的。
因为imax【i】 并不是 imax【i-1】 * Nums【i】或者单纯的Nums【i】。
它需要进行特殊的情况判定。
第三步,特殊情况思考。
正数情况
我们有数组imax,已经从0到i-1都赋值了,并且,他们一定正确。
当Nums【i】为正数时,有2种情况。
假设imax【i-1】 大于 0,则imax【i】 = imax【i-1】 * Nums【i】;
假设imax【i-1】 小于 0,则imax【i】 = Nums【i】;
这没有问题。
负数情况
这时候产生了复杂情况。
imax本身不带有负数资料信息。
也就是说,通过imax数组,不能确定前面有几个负数。
无论是0个、1个、2个或者更多。
我们需要一个辅助数组,记录负数信息。
第四步,负数信息记录思考
我们之前使用过累积量的概念。
但是,很容易发生,这个概念对于imax的提取不完全正确。
对于【2, -5, -2, -4, 3】数组,
累积量数组为
【2, -10, 20, -80, -240】
本身累积量数组,也无法得到imax。
该怎么办呢?
我们知道,在Nums【i】为负数时,算出imax的关键,是得到Nums【i】前面的所有负数(除开第一个和更前面的数组数据)
事实上,对于imax,我们要清楚一件事:
每一个负数个数的变化,都是持续的、可中断的。
假使现在有2个负数,那么计算下一个imax时,至多增加1个负数。
不可能出现,计算下一个imax时,一下子增加2个负数的情况。
那么,我们思考imax的定义下,关于“累积量”的概念。
对于每一个imax【i】,它都一定是一个子序列,这个子序列要满足以下标i结尾,从0到第一个负数舍弃的子序列。
也就是说,imax【i】本身定义了一个累积量。【如果数组全为偶数负数,则全数组都为累积;否则,从第一个负数开始】
然而,我们知道,假设从第一个负数开始,就会遗漏掉0到第一个负数的子序列。
我们需要一个变量Lambda
- 当imax【i】代表着从第一个负数开始时,Lambda能把所有变量都承接;
- 当imax【i】代表着全数组时,Lambda要从第一个负数开始;【以提供imax运算】
第五步,负数信息记录方案
这个Lambda,本质和imax恰好相反。
当imax从全数组开始时,Lambda从第一个负数开始,这就表示Lambda必然是以i结尾的最小的数据。
当imax从第一个负数开始时,Lambda全变量承接,那么,Lambda此时又是以i结尾的最小数据。
也就是说,这可以定义成imin,代表以i结尾的、最小的子序列数据。
第六步,总结
我们要维护2个变量,imax、imin。
这两个变量,恰好分别代表着
imax:以i结尾的最大乘积子序列。
imin:以i结尾的最小乘积子序列。
四、代码结构展示【有数组】
class Solution {public int maxProduct(int[] nums) {// 答案int max = Integer.MIN_VALUE;// 方便操作int len = nums.length;// 临时变量int temp;// 核心变量imax、imin【二者必须同步变化,否则会产生错误】int[] imax = new int[len];int[] imin = new int[len];// 理论上2个变量足够,但是方便测试,用数组// 初始化【我不确定能否在循环里初始化】imax[0] = nums[0];imin[0] = nums[0];max = nums[0];// 由于imax、imin定义为以i结尾的数据,所以理论上只需要遍历1次for(int i=1; i<len; i++){// 于正数if(nums[i] > 0){// 当大于0时,不会增加负根的数量,不会引起偶数、奇数的变化。// 本身imin以>0和反之进行判断,但是恰好可以合并成1个式子imin[i] = Math.min(imin[i-1]*nums[i], nums[i]);// 同理imax[i] = Math.max(imax[i-1]*nums[i], nums[i]);}else if(nums[i] == 0){// 于0时,重新初始化imax[i] = 0;imin[i] = 0;}else{// 会引起偶数、奇数变化imin[i] = Math.min(imax[i-1]*nums[i], nums[i]);imax[i] = Math.max(imin[i-1]*nums[i], nums[i]);}max = Math.max(max, imax[i]);}return max;}
}
五、代码结构展示【经优化,省略数组】
class Solution {public int maxProduct(int[] nums) {// 答案集int max = Integer.MIN_VALUE;// 方便操作int len = nums.length;// 核心变量imax、imin及初始化【二者必须同步变化,否则会产生错误】int imax = nums[0];int imin = nums[0];max = nums[0];// 临时变量,避免imin或imax改变后,影响数据int temp = 0;// 由于imax、imin定义为以i结尾的数据,所以理论上只需要遍历1次for(int i=1; i<len; i++){// 于正数if(nums[i] > 0){// 当大于0时,不会增加负根的数量,不会引起偶数、奇数的变化。// 本身imin以>0和反之进行判断,但是恰好可以合并成1个式子imin = Math.min(imin*nums[i], nums[i]);// 同理imax = Math.max(imax*nums[i], nums[i]);}else if(nums[i] == 0){// 于0时,重新初始化imax = 0;imin = 0;// 这一步,会引起后续正数时,imin的变化嘛?// 或者,后续负数时,imax的变化?// 经过运算,发现不会发生变化,因为变量的变化恰好满足imax、imin的概念定义}else{// 会引起偶数、奇数变化temp = imin;imin = Math.min(imax*nums[i], nums[i]);imax = Math.max(temp*nums[i], nums[i]);}max = Math.max(max, imax);}return max;}
}
六、结语
在力扣题解里,有imin、imax的概念,但我不知其所以然。
在深入地理解时,我愈发发现,imax是原生定义,是做题必然存在的定义,
然而,imin可不是,imin完全属于辅助工具,理论上从0到1就不太可能把它给定义出来。
后来,我发现imin、imax的复杂关系,我试图捋清楚。
我很快弄清楚了,可是imin是如何定义出来的?我还是不理解。
接着,我发现,imax和imin,恰好在奇数负数个数、偶数负数个数互补。
所以,我正好可以写出来。
当然,也有可能完全是我多想了。
以上内容即我想分享的关于力扣热题30的一些知识。
我是蚊子码农,如有补充,欢迎在评论区留言。个人也是初学者,知识体系可能没有那么完善,希望各位多多指正,谢谢大家。
这篇关于算法题解记录30+++乘积最大子序列(百题筑基)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!