연속된 숫자 사이의 차이가 양수와 음수 사이에서 엄격하게 교대로 나타나는 경우 흔들기 수열이라고 하는 일련의 숫자가 있다고 가정합니다. 첫 번째 차이는 양수 또는 음수일 수 있습니다. 요소가 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]
출력
6