LeetCode 2765. 最长交替子数组（枚举、动态规划dp）

2765. 最长交替子数组

思路：状态dp[i]表示的是：以第i个点为结尾的最长交替子数组，时间复杂度0(n)，细节看注释

class Solution {
public:
    int alternatingSubarray(vector<int>& nums) {
        int n=nums.size();
        int dp[110];
        dp[0]=1;
        int maxx=1;
        for(int i=1;i<n;i++){
            dp[i]=1;
            //如果和前面的数差为1
            if(nums[i]-nums[i-1]==1){
            	//判断前面第二个数和当前数是否相等，相等，说明在dp[i-1]的基础上+1
                if(i-2>=0&&nums[i]==nums[i-2]) dp[i]=dp[i-1]+1;
                else dp[i]=2; 
            }
            //如果和前面的数差为-1
            if(nums[i]-nums[i-1]==-1){
            	//判断前面第二个数和当前数是否相等，相等，说明在dp[i-1]的基础上+1，不然就不行。
                if(i-2>=0&&nums[i]==nums[i-2]) dp[i]=dp[i-1]+1;
            }
            maxx=max(maxx,dp[i]);
        }
        if(maxx==1) maxx=-1;
        return maxx;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

优化了一下空间

class Solution {
public:
    int alternatingSubarray(vector<int>& nums) {
        int n=nums.size();
        int cur=1;
        int maxx=1;
        for(int i=1;i<n;i++){
            if(nums[i]-nums[i-1]==1){
                if(i-2>=0&&nums[i]==nums[i-2]) cur++;
                else cur=2;
            }else if(nums[i]-nums[i-1]==-1){
                if(i-2>=0&&nums[i]==nums[i-2]) cur++;
                else cur=1;
            }else cur=1;
            maxx=max(maxx,cur);
        }
        if(maxx==1) maxx=-1;
        return maxx;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20