Make writing a habit together! This is the 7th day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.

The title

If the difference between consecutive numbers alternates strictly between positive and negative numbers, a sequence of numbers is called a swing sequence. The first difference, if one exists, may be positive or negative. Sequences with only one element or two unequal elements are also considered oscillating sequences.

For example, [1, 7, 4, 9, 2, 5] is a swing sequence because the differences (6, -3, 5, -7, 3) alternate between positive and negative values.

Conversely, [1, 4, 7, 2, 5] and [1, 7, 4, 5, 5] are not oscillating sequences, the first sequence because its first two differences are both positive, and the second sequence because its last difference is zero. Subsequences can be obtained by removing some (or none) elements from the original sequence, leaving the remaining elements in their original order.

Given an integer array nums, return the length of the oldest sequence in nums as a swing sequence.

 

Example 1:

Input: nums = [1,7,4,9,2,5] output: 6 explanation: the whole sequence is a swing sequence, the difference between elements is (6, -3, 5, -7, 3).Copy the code

Example 2:

Input: nums =,17,5,10,13,15,10,5,16,8 [1] output: 7: this sequence contains several length is 7 swing sequence. One of them is [1, 17, 10, 13, 10, 16, 8] and the difference between the elements is (16, -7, 3, -3, 6, -8).Copy the code

Example 3:

Input: nums = [1,2,3,4,5,6,7,8,9Copy the code

Tip:

1 <= nums.length <= 1000
0 <= nums[i] <= 1000
Copy the code

Answer key

Analysis of the problem solving

Their thinking

  1. The problem is a typical dynamic programming problem.

  2. Whenever we select an element as part of a swing sequence, the element will either go up or down, depending on the size of the previous element. Then the state expression is listed as:

  • Up [I] represents the length of the longest “ascending swing sequence” ending with one of the previous I elements.

  • Down [I] represents the length of the longest “falling swing sequence” ending with one of the previous I elements.

If there are three cases of up[I],

  • nums[i] > nums[i-1]
up[i] = fmax(up[i-1], down[i-1] + 1);
down[i] = down[i-1];
Copy the code
  • nums[i] < nums[i-1]
up[i] = up[i-1];
down[i] = fmax(up[i-1] + 1, down[i-1]);
Copy the code
  1. And then you get the resultup[numsSize -1], down[numsSize -1].

Complexity Time complexity: O(N) Space complexity: O(N)

The problem solving code

The solution code is as follows (there are detailed notes in the code) :

int wiggleMaxLength(int* nums, int numsSize){
    if (numsSize < 2) {
        return numsSize;
    }

    int up[numsSize], down[numsSize];
up[0]= down[0] =1;
    for (int i=1; i< numsSize; i++) {
        if (nums[i] > nums[i- 1]) {
            up[i] = fmax(up[i- 1], down[i- 1] + 1);
            down[i] = down[i- 1];
        } else if (nums[i] < nums[i- 1]) {
            up[i] = up[i- 1];
            down[i] = fmax(up[i- 1] + 1, down[i- 1]);
        } else {
            up[i] = up[i- 1];
            down[i] = down[i- 1]; }}return fmax(up[numsSize - 1], down[numsSize - 1]);
}
Copy the code

Feedback results after submission (because the topic has not been optimized, the performance is mediocre) :

The reference information

  • Force buckle 376. Swing sequence
  • Dynamic programming