Hãy xem xét một mảng con A [i], A [i + 1], ..., A [j] của A được cho là hỗn loạn khi nó đáp ứng các điều kiện này -
Vì vậy, mảng con sẽ hỗn loạn nếu dấu hiệu so sánh lật giữa từng cặp phần tử liền kề trong mảng con. Bây giờ hãy tìm độ dài của một mảng con hỗn loạn có kích thước lớn nhất là A. Vì vậy, nếu đầu vào là [9,4,2,10,7,8,8,1,9], thì đầu ra là 5. Điều này là do A [1]> A [2] A [4]
Để 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 mảng A
presBig:=1, prevSmall:=1, currBig:=1, currSmall:=1 và ret:=1
cho tôi trong phạm vi từ 1 đến n - 1
trả lại ret
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxTurbulenceSize(vector<int>& A) {
int n = A.size();
int prevBig = 1;
int prevSmall = 1;
int currBig = 1;
int currSmall = 1;
int ret = 1;
for(int i = 1; i < n; i++){
if(A[i] > A[i - 1]){
currBig = 1 + prevSmall;
}
if(A[i] < A[i - 1]){
currSmall = 1 + prevBig;
}
ret = max({ret, currBig, currSmall});
prevSmall = currSmall;
prevBig = currBig;
currSmall = 1;
currBig = 1;
}
return ret;
}
};
main(){
vector<int> v1 = {9,4,2,10,7,8,8,1,9};
Solution ob;
cout << (ob.maxTurbulenceSize(v1));
} Đầu vào
[9,4,2,10,7,8,8,1,9]
Đầu ra
5