题目链接

关键词

解析

• 状态定义：
• max[i]：表示以 nums[i] 为结尾的最大子数组的乘积
• min[i]：表示以 nums[i] 为结尾的最小子数组的乘积

• 为什么需要两个数组？ 因为对于每个状态 dp[i]，都与其前一个状态 dp[i - 1] 以及 当前数 nums[i] 有关的，而且又因为有正负，对于 nums[i] 为正数的情况，我们希望其前一个状态 dp[i - 1] 为最大的正数，对于 nums[i] 为负数的情况，我们希望其前一个状态 dp[i - 1] 为最小的负数，这样才能使得 dp[i] 取 max

• 为什么优化的解法中，可以用滚动数组？ 因为从状态分析中可以知道，每一个 dp[i] 的状态，都只于其前一个状态 dp[i - 1] 有关，所以可以用滚动数组来优化

代码

• 未优化前的代码

• 滚动数组优化后的代码

相似题目