网站建立前期调查,十九冶成都建设有限公司网站,建站系统是什么,南京网站设计公司推荐文章目录 一、题目二、思路三、代码 一、题目 二、思路
#xff08;0#xff09;读懂题意#xff1a;题目的“连续”是指位置的连续#xff0c;而不是说数字的连续#xff0c;这是个大坑。
#xff08;1#xff09;确定状态#xff1a;定义两个状态来记录当前子数组的… 文章目录 一、题目二、思路三、代码 一、题目 二、思路
0读懂题意题目的“连续”是指位置的连续而不是说数字的连续这是个大坑。
1确定状态定义两个状态来记录当前子数组的最大乘积、最小乘积。因为在处理负数时最小乘积乘以负数可能变为最大乘积。dp_max[i]表示以nums[i]结尾的子数组的最大乘积、dp_min[i]表示以nums[i]结尾的子数组的最小乘积。
2状态转移方程对于每个元素nums[i]我们的dp_max[i]和dp_min[i]可以从这三个数中确定
只包含当前元素 nums[i]。当前元素与之前的最大乘积子数组乘积即 dp_max[i-1] * nums[i]。当前元素与之前的最小乘积子数组乘积即 dp_min[i-1] * nums[i]。
即状态转移方程可表示为
dp_max[i] max(nums[i], dp_max[i-1] * nums[i], dp_min[i-1] * nums[i])
dp_min[i] min(nums[i], dp_max[i-1] * nums[i], dp_min[i-1] * nums[i])3初始状态边界条件以第一个元素结尾的子数组最大乘积就是它本身、以第一个元素结尾的子数组最小乘积就是它本身、初始乘积最大结果为第一个元素。
4遍历顺序从左到右遍历数组。
三、代码
方法一按照思路的代码如下时间复杂度为O(n)空间复杂度为O(n)。
class Solution(object):def maxProduct(self, nums)::type nums: List[int]:rtype: intif len(nums) 0:return 0if len(nums) 1:return nums[0]# 初始化数组n len(nums)dp_max [0] * n dp_min [0] * n# 初始状态dp_max[0] nums[0]dp_min[0] nums[0]cheng_ans nums[0]# 从第二个元素开始遍历for i in range(1, n):num nums[i]dp_max[i] max(num, dp_max[i-1]*num, dp_min[i-1]*num)dp_min[i] min(num, dp_max[i-1]*num, dp_min[i-1]*num)cheng_ans max(cheng_ans, dp_max[i])return cheng_ans方法二为了优化空间复杂度发现每次当前只利用前一次状态所以dp_max和dp_min没必要单独用两个数组记录所有的状态。但注意在计算状态转移方程时分别计算dp_max和dp_min都会用到上一次的dp_max和dp_min这为了用错dp_mxn可以直接对num确保是正数后交换dp_max和dp_min的位置减少max和min函数的入参个数。
class Solution(object):def maxProduct(self, nums)::type nums: List[int]:rtype: intif len(nums) 0:return 0if len(nums) 1:return nums[0]# 初始化数组n len(nums)# 初始状态dp_max nums[0]dp_min nums[0]cheng_ans nums[0]# 从第二个元素开始遍历for i in range(1, n):num nums[i]if num 0:dp_max, dp_min dp_min, dp_maxdp_max max(num, dp_max*num)dp_min min(num, dp_min*num)cheng_ans max(cheng_ans, dp_max)return cheng_ans
