Hãy xem xét bất kỳ mảng con B (liền kề) nào (của A) được gọi là núi nếu các thuộc tính sau giữ -
- kích thước của B> =3
- Tồn tại một số 0 B [i + 1]>. ..> B [B.length - 1]
Giả sử chúng ta có một mảng A gồm các số nguyên; chúng ta phải tìm chiều dài của ngọn núi dài nhất. Chúng ta phải trả về 0 nếu không có núi. Vì vậy, nếu đầu vào là [2,1,4,7,3,2,5], thì kết quả sẽ là 5. Vậy ngọn núi lớn nhất sẽ là [1,4,7,3,2], có chiều dài là 5.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- ret:=0, n:=kích thước của mảng a
- i:=0 thành n - 1, tăng i thêm j + 1
- j:=i
- xuống:=false, lên:=false
- while j + 1
a [j] - up:=true và tăng j lên 1
- while up là true và j + 1
a [j] - giảm:=true và tăng j lên 1
- nếu cả tăng và giảm đều đúng, hãy đặt ret:=max của j - i + 1 và ret, giảm j đi 1
- trả lời lại.
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 longestMountain(vector<int>& a) { int ret = 0; int n = a.size(); int j; for(int i = 0; i < n; i = j + 1){ j = i; bool down = false; bool up = false; while(j + 1 < n && a[j + 1] > a[j]) { up = true; j++; } while(up && j + 1 < n && a[j + 1] < a[j]){ down = true; j++; } if(up && down){ ret = max(j - i + 1, ret); j--; } } return ret; } }; main(){ vector<int> v = {2,1,4,7,3,2,5}; Solution ob; cout << (ob.longestMountain(v)); }
Đầu vào
[2,1,4,7,3,2,5]
Đầu ra
5