【算法挨揍日记】day28——413. 等差数列划分、978. 最长湍流子数组

末蓝、 2024-02-19 11:41 49阅读 0赞

## 413. 等差数列划分 ##

[413. 等差数列划分][413.]

### 题目描述： ###

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

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

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

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

![1dd2ed4e2aab4178b22aeb7234b5d6c5.png][]

### 解题思路： ###

1.  状态表⽰：

由于我们的研究对象是「⼀段连续的区间」，如果我们状态表⽰定义成  \[0, i\]  区间内⼀共有多

少等差数列，那么我们在分析  dp\[i\]  的状态转移时，会⽆从下⼿，因为我们不清楚前⾯那么多

的「等差数列都在什么位置」。所以说，我们定义的状态表⽰必须让等差数列「有迹可循」，让状

态转移的时候能找到「⼤部队」。因此，我们可以「固定死等差数列的结尾」，定义下⾯的状态表

⽰：

dp\[i\]  表⽰必须「以  i  位置的元素为结尾」的等差数列有多少种。

2.  状态转移⽅程：

我们需要了解⼀下等差数列的性质：如果  a b c  三个数成等差数列，这时候来了⼀个  d  ，其

中  b c d  也能构成⼀个等差数列，那么  a b c d  四个数能够成等差序列吗？答案是：显然

的。因为他们之间相邻两个元素之间的差值都是⼀样的。有了这个理解，我们就可以转⽽分析我们

的状态转移⽅程了。

对于  dp\[i\]  位置的元素  nums\[i\]  ，会与前⾯的两个元素有下⾯两种情况：

i.  nums\[i - 2\], nums\[i - 1\], nums\[i\]  三个元素不能构成等差数列：那么以

nums\[i\]  为结尾的等差数列就不存在，此时  dp\[i\] = 0  ；

ii.  nums\[i - 2\], nums\[i - 1\], nums\[i\]  三个元素可以构成等差数列：那么以

nums\[i - 1\]  为结尾的所有等差数列后⾯填上⼀个  nums\[i\]  也是⼀个等差数列，此时

dp\[i\] = dp\[i - 1\]  。但是，因为  nums\[i - 2\], nums\[i - 1\], nums\[i\]  三

者⼜能构成⼀个新的等差数列，因此要在之前的基础上再添上⼀个等差数列，于是

dp\[i\] = dp\[i - 1\] + 1  。

综上所述：状态转移⽅程为：

当：  nums\[i - 2\] + nums\[i\] != 2 \* nums\[i - 1\]  时，  dp\[i\] = 0

当：  nums\[i - 2\] + nums\[i\] == 2 \* nums\[i - 1\]  时，  dp\[i\] = 1 + dp\[i -

1\]

3.  初始化：

由于需要⽤到前两个位置的元素，但是前两个位置的元素⼜⽆法构成等差数列，因此  dp\[0\] =

dp\[1\] = 0  。

4.  填表顺序：

毫⽆疑问是「从左往右」。

5.  返回值：

因为我们要的是所有的等差数列的个数，因此需要返回整个  dp  表⾥⾯的元素之和。

### 解题代码： ###

class Solution {
    public:
        int numberOfArithmeticSlices(vector<int>& nums) {
            int n=nums.size();
            vector<int>dp(n,0);
            int ret=0;
            for(int i=2;i<n;i++)
            {
                if((nums[i-1]-nums[i-2])==(nums[i]-nums[i-1]))
                dp[i]=dp[i-1]+1;
                else dp[i]=0;
                ret=ret+dp[i];
            }
            return ret;
        }
    };

## 978. 最长湍流子数组 ##

[978. 最长湍流子数组][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]`。

![48fb7736b3f84db6af081636b191a8ef.png][]

### 解题代码： ###

class Solution {
    public:
        int maxTurbulenceSize(vector<int>& arr) {
            int n = arr.size();
     vector<int> f(n, 1), g(n, 1);
     int ret = 1;
     for(int i = 1; i < n; i++)
     {
     if(arr[i - 1] < arr[i]) f[i] = g[i - 1] + 1;
     else if(arr[i - 1] > arr[i]) g[i] = f[i - 1] + 1;
     ret = max(ret, max(f[i], g[i]));
     }
     return ret;
        }
    };

###  ###

[413.]: https://leetcode.cn/problems/arithmetic-slices/
[1dd2ed4e2aab4178b22aeb7234b5d6c5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/19/df98641245af47bf958bcee72ac5a45a.png
[978.]: https://leetcode.cn/problems/longest-turbulent-subarray/
[48fb7736b3f84db6af081636b191a8ef.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/19/3cca558c929f4ac0915526732420851b.png