Trình tự con lắc lư trong C ++

Giả sử chúng ta có một dãy số được gọi là dãy số lung tung nếu sự khác biệt giữa các số liên tiếp xen kẽ giữa dương và âm. Sự khác biệt đầu tiên có thể là tích cực hoặc tiêu cực. Một chuỗi có ít hơn hai phần tử là một chuỗi không gian tầm thường. Vì vậy, ví dụ, [1,7,4,9,2,5] là một chuỗi lung tung bởi vì nếu bạn thấy, sự khác biệt (6, -3,5, -7,3) là dương và âm luân phiên. Tuy nhiên, [1,4,7,2,5] và [1,7,4,5,5] không phải là chuỗi lung tung, chuỗi thứ nhất vì hai điểm khác biệt đầu tiên là dương và chuỗi thứ hai vì hiệu số cuối cùng của nó bằng 0 .

Vì vậy, chúng ta có một dãy số nguyên, chúng ta phải tìm độ dài của dãy con dài nhất là dãy lung tung. Một dãy con thu được bằng cách xóa một số phần tử (cuối cùng, cũng bằng không) khỏi dãy ban đầu, để lại các phần tử còn lại theo thứ tự ban đầu của chúng. Vì vậy, nếu đầu vào là [1,7,4,9,2,5], thì đầu ra sẽ là 6 vì toàn bộ chuỗi là một chuỗi lung tung.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

n:=kích thước của nums
nếu n là 0, thì trả về 0
thiết lập:=1 trở xuống:=1
cho tôi trong phạm vi từ 1 đến n - 1
- nếu nums [i]> nums [i - 1], thì up:=down + 1
- ngược lại khi nums [i]
trả về tối đa lên và xuống

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int wiggleMaxLength(vector<int>& nums) {
      int n = nums.size();
      if(!n) return 0;
      int up = 1;
      int down = 1;
      for(int i = 1; i < n; i++){
         if(nums[i] > nums[i - 1]){
            up = down + 1;
         }
         else if(nums[i] < nums[i - 1]){
            down = up + 1;
         }
      }
      return max(up, down);
   }
};
main(){
   Solution ob;
   vector<int> v = {1,7,4,9,2,5};
   cout << (ob.wiggleMaxLength(v));
}

Đầu vào

[1,7,4,9,2,5]

Trình tự con lắc lư trong C ++

Ví dụ (C ++)

Đầu vào

Đầu ra