LeetCode brush # 376 # Medium - swing sequence

Discussion on the idea of ​​swing sequence and source code
The topic of swing sequence is as shown in the figure below. This problem belongs to the topic of array class and dynamic programming type. It mainly examines the use of dynamic programming method and the understanding of array structure.The author of the title of this article thinks of two methods, namely the greedy method and the dynamic programming method. The greedy method is written in Java, and the dynamic programming method is written in Python. Of course, this may not be the optimal solution.come up with a faster algorithm.

I think this topic can be solved using the greedy methodTo solve, first initialize the parameters and calculate the length of the array, then start traversing the loop to determine whether each element is greater than the previous element, if so, add 1 to the downtrend parameter and assign it to the uptrend parameter; if it is less than the value of the previous element, thenAdd 1 to the uptrend parameter and assign it to the downtrend parameter until the end of the cycle and judge the larger value of the uptrend parameter and the downtrend parameter as the return result and return.Then according to this idea our Java code is as follows:

#Fire-breathing dragon and water arrow turtleclass Solution {public int wiggleMaxLength(int[] nums) {int downNum = 1;int upNum = 1;int numLen = nums.length;for (int ir = 1; ir < numLen; ir++) {if (nums[ir] > nums[ir - 1])upNum = downNum + 1;else if (nums[ir] < nums[ir - 1])downNum = upNum + 1;}if(numLen==0){return 0;}else{return Math.max(downNum, upNum);}}}

Obviously, our greedy method works well,It can also be solved using dynamic programming methods.First calculate the length of the array to determine whether the length is less than 2, and if so, return the length result directly.Then initialize the uptrend and downtrend parameters to 1, and start traversing the loop to determine whether each element is greater than the previous element. If so, add 1 to the downtrend parameter and assign it to the uptrend parameter; if not, add the uptrend parameter to the uptrend parameter.After 1, it is assigned to the down parameter until the loop traversal ends and the larger value of the up trend parameter and the down trend parameter is judged and the result is returned.So according to this idea, it can be solved, the following is the Python code:

#Fire-breathing dragon and water arrow turtleclass Solution:def wiggleMaxLength(self, nums: List[int]) -> int:numLen = len(nums)if(numLen < 2):return numLenupNum = 1downNum = 1for jr in range(1,numLen):if nums[jr] > nums[jr - 1]:upNum = downNum + 1elif nums[jr] < nums[jr - 1]:downNum = upNum + 1return max(upNum, downNum)

From the results, the Java version of the greedy method is efficient, and the speed of the Python version of the dynamic programming method is also OK, but there should be more methods to further speed up, I hope friends can give me more advice, thank you very much.