算法系列--动态规划--⼦数组、⼦串系列（数组中连续的⼀段）(1)（上）
https://developer.aliyun.com/article/1480827?spm=a2c6h.13148508.setting.14.5f4e4f0eZbJkzo
💕"我们好像在池塘的水底，从一个月亮走向另一个月亮。"💕
作者：Mylvzi
文章主要内容：算法系列–动态规划–⼦数组、⼦串系列（数组中连续的⼀段）(1)
大家好,今天为大家带来的是
算法系列--动态规划--⼦数组、⼦串系列（数组中连续的⼀段）(1),这是动态规划新的一种题型
3.乘积最⼤⼦数组
链接:
https://leetcode.cn/problems/maximum-product-subarray/
分析:
首先想到的状态表示就是以i位置为结尾子数组的最大乘积,但是根据这个状态表示去推到状态转移方程时发现只使用一个dp表无法表示所有的情况
- 当
nums[i] > 0,i位置的状态就是前一个位置的最大乘积 * nums[i] - 当
nums[i] < 0,此时无法通过dp[i - 1]来推到dp[i],因为一个负数 * 较大的数一定会变小,那么dp[i]存储的就是以i位置为结尾的子数组的最小乘积,这与我们的状态表示是矛盾的
既然当nums[i] < 0时,需要乘的是以i-1位置为结尾的子数组的最小乘积,那么我们就创建出一个dp表g[i]来表示最小乘积,以下是详细分析过程:
代码:
class Solution { public int maxProduct(int[] nums) { // 创建dp表 int n = nums.length; int[] f = new int[n]; int[] g = new int[n]; // 初始化 f[0] = g[0] = nums[0]; int max = f[0]; // 填表 for(int i = 1; i < n; i++) { int t1 = 0, t2 = 0; if(nums[i] > 0) { f[i] = f[i - 1] * nums[i]; g[i] = g[i - 1] * nums[i]; }else { f[i] = g[i - 1] * nums[i]; g[i] = f[i - 1] * nums[i]; } f[i] = Math.max(nums[i],f[i]); g[i] = Math.min(nums[i],g[i]); max = Math.max(f[i],max); } return max; } }
4.乘积为正数的最⻓⼦数组
链接:
https://leetcode.cn/problems/maximum-length-of-subarray-with-positive-product/description/
分析:
本题相较于上题有两个不同:
- 本题要求乘积必须为正数
- 本题求解的不是最大的乘积,而是乘积为正数的最长子数组
和上题一样,本题同样需要使用两个dp表来进行状态表示
f[i]:以i位置为结尾,乘积为正数的最大子数组长度g[i]:以i位置为结尾,乘积为负数的最大子数组长度
状态转移方程推导如下:
注意特殊情况:
- 当n[i] < 0时,
f[i] == g[i - 1] + 1,但是如果i位置之前全是正数,此时g[i - 1] == 0,那么f[i] == 0 + 1 = 1了,但是因为n[i] < 0,i位置的f[i]应该等于 0,因为所有的以i位置为结尾的子数组的乘积必然为负数
代码:
class Solution { public int getMaxLen(int[] nums) { int n = nums.length; // 1.创建dp表 int[] f = new int[n]; int[] g = new int[n]; // 2.根据状态表示进行初始化 f[0] = nums[0] > 0 ? 1 : 0; g[0] = nums[0] < 0 ? 1 : 0; int max = -0x3f3f3f3f; // 3.填表 for(int i = 1; i < n; i++) { if(nums[i] > 0) { f[i] = f[i - 1] + 1; g[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1; }else if(nums[i] < 0){ f[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1; g[i] = f[i - 1] + 1; }else { f[i] = g[i] = 0;// 注意等于0相当于直接截断 要重新计数 从0开始 } max = Math.max(f[i],max);// 更新长度 } // 处理n == 1的情况 return max == -0x3f3f3f3f ? f[0] : max; } }
总结:
- 子数组问题最常用的一种状态表示就是
以i位置为结尾的xxxx - 在推导状态转移方程时,往往是根据
组成子数组的形态来分类讨论(单独一个还是和前面一堆组成子数组)
