C++刷leetcode（376. 摆动序列）【动态规划】

糖逗

题目描述：

1. 如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。
   
2. 
   
3. 例如， [1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
   
4. 
   
5. 给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。
   
6. 
   
7. 示例 1:
   
8. 
   
9. 输入: [1,7,4,9,2,5]
   
10. 输出: 6
    
11. 解释: 整个序列均为摆动序列。
    
12. 示例 2:
    
13. 
    
14. 输入: [1,17,5,10,13,15,10,5,16,8]
    
15. 输出: 7
    
16. 解释: 这个序列包含几个长度为 7 摆动序列，其中一个可为[1,17,10,13,10,16,8]。
    
17. 示例 3:
    
18. 
    
19. 输入: [1,2,3,4,5,6,7,8,9]
    
20. 输出: 2
    
21. 
    
22. 来源：力扣（LeetCode）
    
23. 链接：https://leetcode-cn.com/problems/wiggle-subsequence
    
24. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. #include <iostream>
   
2. #include <vector>
   
3. using namespace std;
   
4. 
   
5. int solution(vector<int>& nums) {
   
6.     if(nums.size() < 1) return 0;
   
7.     vector<int> input;//去重，去除连续相等的适?
   
8.     input.push_back(nums[0]);
   
9.     for(int i = 1; i<nums.size(); i++){
   
10.         if(nums[i] != nums[i-1]) input.push_back(nums[i]);
    
11.     }
    
12.     //对新生成的数列进行动态规划
    
13.     int length = input.size();
    
14.     if(length < 2) return length;
    
15.     int dp[length];
    
16.     dp[0] = 1, dp[1] = 2;
    
17.     for(int i = 2; i < length; i++){
    
18.         if((input[i]-input[i-1]) * (input[i-1]- input[i-2]) < 0){
    
19.             dp[i] = dp[i-1] + 1;
    
20.         }
    
21.         else{
    
22.             dp[i] = dp[i-1];
    
23.         }
    
24.         
    
25.     }
    
26.     return dp[length-1];
    
27. }
    
28. 
    
29. 
    
30. int main(void){
    
31.         vector<int> input;
    
32.         int number;
    
33.         while(cin >> number){
    
34.                 input.push_back(number);
    
35.         }
    
36.         cout << solution(input) << endl;
    
37. 
    
38.         return 0;
    
39. }
    
40. 
    
41. 
    

复制代码

注意事项：
1、先去重