C++의 흔들기 하위 시퀀스

<시간/>

연속된 숫자 사이의 차이가 양수와 음수 사이에서 엄격하게 교대로 나타나는 경우 흔들기 수열이라고 하는 일련의 숫자가 있다고 가정합니다. 첫 번째 차이는 양수 또는 음수일 수 있습니다. 요소가 2개 미만인 시퀀스는 쉽게 흔들기 시퀀스입니다. 예를 들어 [1,7,4,9,2,5]는 흔들기 시퀀스입니다. 왜냐하면 차이(6,-3,5,-7,3)가 교대로 양수와 음수이기 때문입니다. 그러나 [1,4,7,2,5]와 [1,7,4,5,5]는 흔들기 시퀀스가 아닙니다. 첫 번째 것은 처음 두 차이가 양수이기 때문에, 두 번째 것은 마지막 차이가 0이기 때문에 .

그래서 우리는 일련의 정수를 가지고 있습니다. 우리는 흔들기 시퀀스인 가장 긴 부분 시퀀스의 길이를 찾아야 합니다. 부분 시퀀스는 원래 시퀀스에서 몇 가지 요소(결국에는 0도 포함)를 삭제하고 나머지 요소는 원래 순서대로 유지하여 얻습니다. 따라서 입력이 [1,7,4,9,2,5]와 같으면 전체 시퀀스가 흔들기 시퀀스이므로 출력은 6이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n :=숫자 크기
n이 0이면 0을 반환합니다.
설정 :=1 및 아래로 :=1
범위 1에서 n – 1까지의 i에 대해
- nums[i]> nums[i – 1]이면 위 :=아래로 + 1
- 그렇지 않으면 nums[i]
위아래로 최대값을 반환

예시(C++)

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

#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));
}

입력

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