Greed - 376. Swing sequence

1 Title Description

If the difference between consecutive numbers strictly alternates between positive and negative numbers , Then the sequence of numbers is called Swing sequence . First difference （ If it exists ） It could be positive or negative . A sequence with only one element or two unequal elements is also regarded as a swing sequence .

for example , [1, 7, 4, 9, 2, 5] It's a Swing sequence , Because of the difference (6, -3, 5, -7, 3) It's alternating positive and negative .

contrary ,[1, 4, 7, 2, 5] and [1, 7, 4, 5, 5] It's not a wobble sequence , The first sequence is because its first two differences are positive , The second sequence is because its last difference is zero .
Subsequence You can delete some... From the original sequence （ It can also be done without deleting ） Element to get , The remaining elements keep their original order .

Give you an array of integers nums , return nums As Swing sequence Of The length of the longest subsequence .

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/wiggle-subsequence

2 Title Example

Example 1：
Input ：nums = [1,7,4,9,2,5]
Output ：6
explain ： The whole sequence is a swing sequence , The difference between the elements is (6, -3, 5, -7, 3) .

Example 2：
Input ：nums = [1,17,5,10,13,15,10,5,16,8]
Output ：7
explain ： This sequence contains several lengths of 7 Swing sequence .
One of them is [1, 17, 10, 13, 10, 16, 8] , The difference between the elements is (16, -7, 3, -3, 6, -8) .

Example 3：
Input ：nums = [1,2,3,4,5,6,7,8,9]
Output ：2

3 Topic tips

1 <= nums.length <= 1000
0 <= nums[i] <= 1000

4 Ideas

The solution of this problem comes from the code Capriccio , This is also the order in which I brush questions , I recommend you to use
link ： greedy ——376. Swing sequence
This question requires deleting some... From the original sequence ( It can also be done without deleting ) Element to get the subsequence , The remaining elements keep their original order .
I believe this statement scares many students , This requires that the maximum swing sequence can modify the array , How to modify this ?
So let's analyze that , It is required to delete the element to reach the maximum swing sequence , What elements should be deleted ?
Use example 2 to illustrate , As shown in the figure :

Local optimum : Delete nodes on monotonic slopes ( Nodes at both ends of monotonic slope are not included ), Then this slope can have two local peaks .
The overall best : The whole sequence has the most local peaks , So as to achieve the longest swing sequence .
The local optimum leads to the global optimum , There is no counter example , Then try greed !
( To express for convenience , The peaks mentioned below refer to local peaks )
In practice , In fact, you don't even need to delete , Because the title requires the length of the longest swing subsequence , So you just need to count the peak number of the array ( It is equivalent to deleting the order — Nodes on the slope , Then count the length )
This is what greed is for , Keep the peak as high as possible , Then delete the order — Nodes on the slope .
The code implementation of this problem , There are also some techniques , For example, when counting the peak , The leftmost and rightmost sides of the array are the worst Statistics .
For example, the sequence [2.5], Its peak number is 2, If you calculate the number of peaks by statistical difference, you need to consider the special cases of the leftmost and rightmost sides of the array .
So you can target the sequence [2.5], We can assume that [2,2.5], So it has a slope, that is preDiff =0, Pictured :
In view of the above situation ,result For the initial 1( By default, there is a peak on the far right ), here curDiff > 0 && preDiff <= 0, that result++( The peak value on the left is calculated ), final result Namely 2( The number of peaks is 2 That is, the length of the swing sequence is 2)
Time complexity ：O(n)
Spatial complexity ：O(1)

5 My answer

// DP
class Solution {
    
    public int wiggleMaxLength(int[] nums) {
    
        // 0 i  As the maximum length of the wave crest 
        // 1 i  As the maximum length of the trough 
        int dp[][] = new int[nums.length][2];

        dp[0][0] = dp[0][1] = 1;
        for (int i = 1; i < nums.length; i++){
    
            //i  You can be a crest or trough 
            dp[i][0] = dp[i][1] = 1;

            for (int j = 0; j < i; j++){
    
                if (nums[j] > nums[i]){
    
                    // i  It's a trough 
                    dp[i][1] = Math.max(dp[i][1], dp[j][0] + 1);
                }
                if (nums[j] < nums[i]){
    
                    // i  It's the crest 
                    dp[i][0] = Math.max(dp[i][0], dp[j][1] + 1);
                }
            }
        }

        return Math.max(dp[nums.length - 1][0], dp[nums.length - 1][1]);
    }
}

class Solution {
    
    public int wiggleMaxLength(int[] nums) {
    
        if (nums.length <= 1) {
    
            return nums.length;
        }
        // Current difference 
        int curDiff = 0;
        // Last difference 
        int preDiff = 0;
        int count = 1;
        for (int i = 1; i < nums.length; i++) {
    
            // Get the current difference 
            curDiff = nums[i] - nums[i - 1];
            // If the current difference and the previous difference are one positive and one negative 
            // be equal to 0 The case of represents the initial preDiff
            if ((curDiff > 0 && preDiff <= 0) || (curDiff < 0 && preDiff >= 0)) {
    
                count++;
                preDiff = curDiff;
            }
        }
        return count;
    }
}