376. Swing sequence [greedy, dynamic planning -----]

376. Swing sequence
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 .

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

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

---

greedy ：

• Only 1 Number ：[3]
  if (len < 2) return len;
• Only 2 Number ：[3,3]、[3,5] （ Two cases ）
  int count = preNum == 0 ? 1 : 2;
• More than one number ：[3,3,3,3,5,2]、[3,3,3,3,1,5] , So judgment is needed preNum >= 0、preNum <= 0 :
  if ((preNum >= 0 && curNum < 0) || (preNum <= 0 && curNum > 0))
• Iterative framework ：

int preNum = nums[1] - nums[0];
for ( …… ) {
    
        int curNum = nums[i] - nums[i-1];
        if ( …… ) {
    
            ++count;
            preNum = curNum;
        }
 }

Java Code 1： greedy

class Solution {
    
    public int wiggleMaxLength(int[] nums) {
    
        int len = nums.length;
        if (len < 2) return len;
        int preNum = nums[1] - nums[0];
        int count = preNum == 0 ? 1 : 2;
        for (int i = 2; i < len; i++) {
    
            int curNum = nums[i] - nums[i - 1];
            if ((preNum >= 0 && curNum < 0) || (preNum <= 0 && curNum > 0)) {
    
                ++count;
                preNum = curNum;
            }
        }
        return count;
    }
}

---

Java Code 2： Dynamic programming

 Insert a code chip here