Computer >> Máy Tính >  >> Lập trình >> C ++

Ngọn núi dài nhất trong mảng trong C ++

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