[dp8_子数组] 乘积为正数的最长子数组长度 | 等差数列划分 | 最长湍流子数组

目录

1.乘积为正数的最长子数组长度

2.等差数列划分

3.最长湍流子数组

---

• 写代码做到，只用维护好自己的一小步

1.乘积为正数的最长子数组长度

链接：1567. 乘积为正数的最长子数组长度

给你一个整数数组 nums ，请你求出乘积为正数的最长子数组的长度。

一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。

请你返回乘积为正数的最长子数组长度。

示例 1：

输入：nums = [1,-2,-3,4]
输出：4
解释：数组本身乘积就是正数，值为 24 。

示例 2：

输入：nums = [0,1,-2,-3,-4]
输出：3
解释：最长乘积为正数的子数组为 [1,-2,-3] ，乘积为 6 。
注意，我们不能把 0 也包括到子数组中，因为这样乘积为 0 ，不是正数。

---

• 在上一题当中我们求过了，乘积最大的子数组，现在我们找的是乘积为正数的，最长的子数组
• 我们该如何分析这个状态呢

求乘积为正数最大子数组长度。

---

1.状态表示

• 经验 + 题目要求
• dp[i] 表示 ：以 i 位置元素为结尾的所有子数组中乘积为正数的最大长度

还是先以这个分析

• i 本身也是子数组，然后为空看nums[i] 是正还是负。
• 还有以 i 位置为结尾的子数组，求所有子数组中乘积为正数的最大长度，nums[i]要分正还是负，剩下的子数组都有一个特点就是以 i - 1结尾
• 所以我们可以将以 i -1 位置元素为结尾的所有子数组中乘积为正数的最大长度拿到
• 然后在加上nums[i]为正为负的情况。

我们由上面的状态表示去分析，发现当子数组长度大于1，nums[i] < 0，分析不下去了，如果前面 i - 1 位置有乘积为负数最大长度，负数乘nums[i] > 0，乘积也大于0，那长度不也应该加+1嘛。

• 所以一个状态表示不够。
• f[i] 表示：以 i 位置元素为结尾所有子数组中乘积为正数的最大长度
• g[i] 表示：以 i 位置元素为结尾所有子数组中乘积为负数的最大长度
• 然后再结合上自身的正负，对于F和G的选择进行考虑

2.状态转移方程

我们先来分析一下 f

当长度大于1，nums[i] < 0，所以我们要找到的是 i - 1位置元素为结尾所有子数组中乘积为负数的最大长度，但是要注意的是

• 万一 g[i - 1] 位置为0呢？也就是说前面根本就没有乘积为负数的最大长度。
• 那所以继续保持为零即可

因此这里不能这样写，需要判断一下：

• g[i-1]==0?0:g[i-1]+1

再来分析一下g

长度大于1，nums[i] > 0，所以我们要找到的是 i - 1位置元素为结尾所有子数组中乘积为负数的最大长度

• 但是万一 g[i - 1] 是 0呢？
• 乘积不可能为负，而nums[i] > 0，这种情况以 i 位置元素为结尾所有子数组中乘积为负数的最大长度就是0，因此下面写的就不对。

正确写法：

• g[i-1]==0?0:g[i-1]+1

有人可能会有疑问：为什么f 当长度大于1，nums[i] > 0，不去考虑 f[i -1] 为0的情况呢

• 其实我们已经考虑过了，f[i -1] 为0就为0好了，反正nums[i] > 0至少有1个。
• 同样g 当长度大于1，nums[i] < 0， 不去考虑 f[i -1]为0的情况，都是一样的
• f[i -1] 为0就为0好了，反正nums[i] < 0至少有1个。如果大于0 就加上好了。

下面可以整体一下状态转移方程

• f[i]，可以把 nums[i] > 0 两种情况合并成 f[i - 1] + 1，因为nums[i] > 0 至少保证有一个了，如果f[i - 1] == 0 最终结果可以是两个1中任何一个
• 如果 f[i - 1] > 0，最大值是由f[i - 1] + 1来决定，所以不用考虑上面单独1了。
• nums[i] < 0 两种情况合并成 g[i -1] ==
• z0 ？：g[i -1] + 1，要么是0，要么是比0更大的数，最大值由g[i -1] == 0 ？：g[i -1]决定
• 注意因为这个地方求的是长度，长度就只有零和一之分，所以是可以这么合并的

同理g也是这样合并

(维护 g 表其实就是为了对负数做处理，要运用到负负得正)

3.初始化

注意到填表填 0 位置的时候会越界。我们这里可以多申请一个节点

1. 里面的值要保证后面填表的正确
2. 下标映射关系

考虑没有填表的时候g第一个位置填什么，nums[0] > 0 填0，nums[0] < 0填1。
代入是不是f[i - 1] 和 g[i -1] 的位置都填0啊，所以虚拟节点填0。

• 原数组对应的下标要-1

4.填表顺序

• 从左往右
• 两个表一起填

5.返回值

• f表中最大值

class Solution {
public:int getMaxLen(vector<int>& nums) {int n=nums.size();vector<int> f(n+1);auto g=f;for(int i=1;i<=n;i++){//下表映射if(nums[i-1]>0){f[i]=f[i-1]+1;g[i]=g[i-1]==0?0:g[i-1]+1;}if(nums[i-1]<0){f[i]=g[i-1]==0?0:g[i-1]+1;g[i]=f[i-1]+1;}}int ret=0;for(int i=1;i<=n;i++){ret=max(ret,f[i]);}return ret; }
};

---

2.等差数列划分

链接： 413. 等差数列划分

如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。

• 例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。

给你一个整数数组 nums ，返回数组 nums 中所有为等差数组的 子数组 个数。

子数组 是数组中的一个连续序列。

示例 1：

输入：nums = [1,2,3,4]
输出：3
解释：nums 中有三个子等差数组：[1, 2, 3]、[2, 3, 4] 和 [1,2,3,4] 自身。

示例 2：

输入：nums = [1]
输出：0

---

• 如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。
• 返回数组 nums 中所有为等差数组的 子数组 个数。

算法原理：

1.状态表示

• 经验 + 题目要求
• 以 i 位置为结尾，巴拉巴拉。
  题目要求，求数组中为等差数组的子数组个数，也就是子数组中有多少个等差数列
• dp[i] 表示：以 i 位置元素为结尾的所有子数组中有多少个等差数列。

2.状态转移方程

• 如果[a, b, c, d]已经构成一个等差数列，d后面在加一个e，与c、d、e构成等差数列，[a, b, c, d, e]也是构成等差数列。
• dp[i] 表示：以 i 位置元素为结尾的所有子数组中有多少个等差数列。子数组要求是连续的
• 所以求 i 位置，要先去看 i -1 和 i - 2 cvs 的位置。
• i - 2 位置元素设为a，i - 1 位置元素设为b、i 位置元素设为c

先考虑a、b、c是否构成一个等差数列。

• 如果abc能构成一个等差数列，那就是以ab为结尾的等差数列后面在加一个c，这些数列也是构成一个等差数列，以ab为结尾就相当于以b为结尾，以b为结尾的等差数列，就在dp[i-1]存着。别忘记 abc也能构成一个等差数列。
• abc不能构成一个等差数列，即使a前面能构成等差数列，但是与 i 位置不连续，因此就构不成以 i 位置为结尾的等差数列

3.初始化

• 这里我们可以直接把dp[0] = dp[1] = 0
• 注意重新的下标映射

4.填表顺序

• 从左往右

5.返回值

• 注意并不是返回最后一个位置，题目要求找的是所有等差数列的个数，因此我们返回的是dp表所有元素的和。

class Solution {
public:int numberOfArithmeticSlices(vector<int>& nums) {//a b cint n=nums.size();if(n<2) return 0;vector<int> dp(n);dp[0]=0,dp[1]=0; //将前两个位置初始为零for(int i=2;i<n;i++){//下标映射int a=nums[i-2],b=nums[i-1],c=nums[i];dp[i]=(c-b==b-a?dp[i-1]+1:0); //填表//如果可以，那个状态就可以延续过来}//求和int ret=0;for(int i=0;i<n;i++){ret+=dp[i];}return ret;}
};

---

3.最长湍流子数组

链接： 978. 最长湍流子数组

给定一个整数数组 arr ，返回 arr 的 最大湍流子数组的长度 。

如果比较符号在子数组中的每个相邻元素对之间翻转，则该子数组是 湍流子数组 。

更正式地来说，当 arr 的子数组 A[i], A[i+1], ..., A[j] 满足仅满足下列条件时，我们称其为湍流子数组：

• 若 i <= k < j ：

• • 当 k 为奇数时， A[k] > A[k+1]，且
  • 当 k 为偶数时，A[k] < A[k+1]；

• 或 若 i <= k < j ：

• • 当 k 为偶数时，A[k] > A[k+1] ，且
  • 当 k 为奇数时， A[k] < A[k+1]。

示例 1：

输入：arr = [9,4,2,10,7,8,8,1,9]
输出：5
解释：arr[1] > arr[2] < arr[3] > arr[4] < arr[5]

示例 2：

输入：arr = [4,8,12,16]
输出：2

---

• 给定一个整数数组 arr ，返回 arr 的 最大湍流子数组的长度 。
• 如果比较符号在子数组中的每个相邻元素对之间翻转，则该子数组是 湍流子数组 。

湍流子数组到底什么东西，我们举个例子，比如说下面，元素大小呈现一升一降的趋势这就是湍流数组。那就称这个数组是湍流子数组。

• 本身 也算湍流 子数组

算法原理：

1.状态表示

• 经验 + 题目要求
• 以 i 位置为结尾，巴拉巴拉

要求找子数组中最大湍流长度。

• dp[i] 表示：以 i 位置元素为结束的所有子数组中，最大湍流数组的长度

根据最近的一步分析问题，设 i - 1 位置元素为 a，i 位置元素为 b。此时会有三种情况。

• a > b i位置最后呈现下降趋势
  a < b i位置最后呈现上升趋势
  a == b i位置最呈现平稳趋势

但是我们的状态表示只是表示 以 i 位置元素为结束的所有子数组中，最大湍流数组的长度

并没有分是上升趋势还是下降趋势。

因此一个状态表示不能满足现在的情况。所以我们要换状态表示。

• f[i] 表示：以 i 位置元素为结尾的所有子数组中，最后呈现 “上升” 状态下的最长湍流数组的长度
• g[i] 表示：以 i 位置元素为结尾的所有子数组中，最后呈现 “下降” 状态下的最长湍流数组的长度

2.状态转移方程

• 先来分析f表
  当a > b i 位置最后呈现下降趋势，但是f表要的是 i 位置最后呈现上升趋势，别忘记本身也可以是湍流子数组，因此是1
• 当a < b i 位置最后呈现上升趋势，去 i - 1位置找到以 i - 1位置为结尾最后呈现下降趋势的最长湍流数组的长度这个就在 g[i - 1]存着，最后别忘记加上1
• 当 a == b，本身也可以是湍流子数组，因此是1

g表分析和f表分析一样，可以自己试着分析一下。

• 当a > b i 位置最后呈现下降趋势，去 i - 1位置找到以 i - 1位置为结尾最后呈现上升趋势的最长湍流数组的长度这个就在 f[i - 1]存着，最后别忘记加上1
• 当a < b i 位置最后呈现上升趋势，但是g表要的是 i 位置最后呈现下降趋势，别忘记本身也可以是湍流子数组，因此是1
• 当 a == b，本身也可以是湍流子数组，因此是1

3.初始化

填第一个位置会越界，可以把第一个位置初始化，注意本身也可以是湍流子数组，因此第一个位置可以初始化为1

• 不过这里我们可以把数组初始化都为1，这样的话
  f表 a > b 和 a == b ，g表 a < b 和 a == b
• 填表的时候就不用考虑了，反正f[i]和g[i]都已经初始化为1了。

4.填表顺序

• 从左往右
• 两个表一起填

5.返回值

• 我们要的是子数组中最大湍流数组的长度，因此是找两个表里面的最大值。

class Solution {
public:int maxTurbulenceSize(vector<int>& arr) {int n=arr.size();vector<int> f(n,1);//本身也是湍流auto g=f;//统计以各个点为结尾 的 长度for(int i=1;i<n;i++){int a=arr[i-1],b=arr[i];if(a>b){f[i]=1;g[i]=f[i-1]+1;}if(a<b){f[i]=g[i-1]+1;g[i]=1;}}int ret=0;for(int i=0;i<n;i++){ret=max(ret,max(f[i],g[i]));}return ret;}
};