Topic:
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. A sequence with less than two elements is also a swing sequence.
For example, [1,7,4,9,2,5] is a wobble 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.
Given a sequence of integers, returns the length of the oldest sequence as the swing sequence. Subsequences are obtained by removing some (or none) elements from the original sequence, leaving the remaining elements in their original order.
Example:
- Example 1:
Input:,7,4,9,2,5 [1]
Output: 6
Explanation: The whole sequence is oscillating sequence.
Copy the code- Example 2:
Input:,17,5,10,13,15,10,5,16,8 [1]
Output: 7
Explanation: this sequence contains several oscillations of length 7, one of which can be [1,17,10,13,10,16,8].
Copy the code- Example 2:
Input:,2,3,4,5,6,7,8,9 [1]
Output: 2
Copy the codeTip:
- Given a string length between [1, 10,000].
The topic
Given an array of integers, find the sequence in which the differences of two contiguous elements are alternately greater than 0 to less than 0 or less than 0 to greater than 0.
Train of thought
Dynamic programming
Dynamic programming: The problem is broken down into relatively simple sub-problems
In this case, the question is to find the longest swingle subsequence. The subproblem is: if an element is added to numS, the swingle subsequence can be added to the subsequence, and whether the swingle subsequence formed after the addition becomes longer
The subsequence can be divided into upDp (the last two numbers are greater than 0) and downDp (the last two numbers are less than 0) according to the last ‘wobble’ state of the wobble subsequence.
Nums adds a new element to its oscillating subsequence:
- The new element is greater than the previous element
- If the original oscillating subsequence is in the descending state, new elements can be added and the subsequence state becomes the ascending state
- If the original oscillating subsequence is in the ascending state, the element cannot enter the subsequence and the subsequence state remains unchanged
- Retain the maximum length of subsequences in both cases
- The new element is smaller than the previous element
- If the original oscillating subsequence is in the ascending state, new elements can be added and the subsequence state becomes the descending state
- If the original oscillating subsequence is in a descending state, the element cannot enter the subsequence and the subsequence state remains unchanged
- Retain the maximum length of subsequences in both cases
- The new element is equal to the previous element, and the state of the subsequence is unchanged
Finally, the maximum length of swingle subsequence in ascending state and descending state is returned
/ * *
* @param {number[]} nums
* @return {number}
* /
var wiggleMaxLength = function(nums) {
let len = nums.length
if (len < 2) return len
// Initialize the subsequence length to reach different nums positions and states
let upDp = Array(len).fill(0),
downDp = Array(len).fill(0)
upDp[0] = downDp[0] = 1
for (let i = 1; i < len; i++) {
// The new element is larger than the previous element, and the original descending state +1 becomes the ascending state
if (nums[i] > nums[i - 1]) {
upDp[i] = Math.max(upDp[i - 1], downDp[i - 1] + 1)
downDp[i] = downDp[i - 1]
} else if (nums[i] < nums[i - 1]) {
// The new element is less than the previous element, and the original up state +1 becomes the down state
upDp[i] = upDp[i - 1]
downDp[i] = Math.max(upDp[i - 1] + 1, downDp[i - 1])
} else {
upDp[i] = upDp[i - 1]
downDp[i] = downDp[i - 1]
}
}
// Returns the maximum length of a subsequence that ends in different states
return Math.max(upDp[len - 1], downDp[len - 1])
}
Copy the codeTo optimize the
As can be seen from the above logic, upDp and downDp respectively depend on the last calculation, so they can be simplified into number: up and down to record the maximum length of subsequences of different states.
Because of swing subsequence, two kinds of state should be appear alternately, namely | up – down | < = 1, so on
Math. Max (upDp[i-1], downDp[i-1] +1) => down+1;
var wiggleMaxLength = function(nums) {
let len = nums.length
if (len < 2) return len
let up = (down = 1)
for (let i = 2; i < len; i++) {
if (nums[i] > nums[i - 1]) {
up = down + 1
} else if (nums[i] < nums[i - 1]) {
down = up + 1
}
}
return Math.max(up, down)
}
Copy the codeBlog: Front end little bookboy
Every day a daily problem, write the solution of the problem will be updated to the public account one day a big Lee column welcome to pay attention to the message
Public number: front end little bookboy