【动态规划算法练习】day12

摘星

发布于 2023-10-15 15:47:56

2180

一、978. 最长湍流子数组

1.题目简介

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]。

2.解题思路

3.代码

class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {
        vector<int> dp(arr.size(), 1);//至少有自己一个元素作为湍流数组
        //dp[i]表示以i元素结尾的湍流数组的最大长度
        int ret = 1;
        int prev = 0, cur = 0;
        for(int i = 1;i < arr.size(); ++i)
        {
            cur = arr[i] - arr[i - 1];
        //1.如果当前元素与它之前的两个元素可以构成湍流数组，则它可以加入以i-1为结尾的湍流数组，组成一个更大的数组
        //2.如果当前元素与它之前的两个元素不可以构成湍流数组，但它和前一个元素不相同，则它和前一个元素组成一个湍流数组
        //3.如果当前元素与它之前的两个元素不可以构成湍流数组，同时它与前一个元素相同，则它只能自己是一个湍流数组
            if((prev == 0 && cur != 0) || (prev < 0 && cur > 0) || (prev > 0 && cur < 0))
            {
                dp[i] = dp[i - 1] + 1;
            }
            else if(arr[i] != arr[i - 1])
            {
                dp[i] = 2;
            }
            ret = max(ret, dp[i]);
            prev = cur;
        }
        return ret;
    }
};

4.运行结果

二、413. 等差数列划分

1.题目简介

413. 等差数列划分如果一个数列至少有三个元素，并且任意两个相邻元素之差相同，则称该数列为等差数列。例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。给你一个整数数组 nums ，返回数组 nums 中所有为等差数组的子数组个数。子数组是数组中的一个连续序列。

2.解题思路

3.代码

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        if(nums.size() < 3) return 0;
        vector<int> dp(nums.size(), 0);
        //dp[i]表示以i为结尾的等差数列个数
        int ret = 0;
        int prev = 0, cur = 0;
        for(int i = 2;i < nums.size(); ++i)
        {
            prev = nums[i - 1] - nums[i - 2];
            cur = nums[i] - nums[i - 1];
            if(prev == cur)
            {
                dp[i] = dp[i - 1] + 1;
            }
            prev = cur;
            ret += dp[i];
        }
        return ret;
    }
};

4.运行结果

三、1567. 乘积为正数的最长子数组长度

1.题目简介

1567. 乘积为正数的最长子数组长度给你一个整数数组 nums ，请你求出乘积为正数的最长子数组的长度。一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。请你返回乘积为正数的最长子数组长度。

2.解题思路

3.代码

class Solution {
public:
    int getMaxLen(vector<int>& nums) {
        vector<int> f(nums.size(), 0);//f[i]表示以i元素为结尾的乘积为正书的最长子数组的长度
        vector<int> g(nums.size(), 0);//f[i]表示以i元素为结尾的乘积为负书的最长子数组的长度
        int ret = 0;
        //初始化(初始化第一个元素对应的dp数组值)
        if(nums[0] > 0)
        {
            f[0] = 1;
            ret = 1;
        }
        else if(nums[0] < 0)
        {
            g[0] = 1;
        }
        for(int i = 1;i < nums.size(); ++i)
        {
            if(nums[i] > 0)
            {
                if(f[i - 1])//如果正数数组有值，则它与正数的乘积为正数
                f[i] = f[i - 1] + 1;
                else
                f[i] = 1;
                if(g[i - 1])//如果负数数组有值，则它与正数的乘积为负数
                g[i] = g[i - 1] + 1;
            }
            else if(nums[i] < 0)
            {
                if(g[i - 1])//如果负数数组有值，则它与负数的乘积为正数
                f[i] = g[i - 1] + 1;
                if(f[i - 1])//如果正数数组有值，则它与负数的乘积为负数
                g[i] = f[i - 1] + 1;
                else
                g[i] = 1;
            }
            else
            {
                f[i] = g[i] = 0;
            }
            ret = max(ret, f[i]);
        }
        return ret;
    }
};