ภูเขาที่ยาวที่สุดใน Array ใน C++

สมมติว่าเรามีอาร์เรย์ A ของจำนวนเต็ม เราต้องหาความยาวของภูเขาที่ยาวที่สุด เราต้องคืนค่า 0 หากไม่มีภูเขา ดังนั้นหากอินพุตเป็นเช่น [2,1,4,7,3,2,5] ผลลัพธ์จะเป็น 5 ดังนั้นภูเขาที่ใหญ่ที่สุดจะเป็น [1,4,7,3,2] ซึ่งมีความยาว 5.

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ret :=0, n :=ขนาดของอาร์เรย์ a
• i :=0 ถึง n – 1, เพิ่ม i โดย j + 1
  • j :=ฉัน
  • ลง :=เท็จ ขึ้น :=เท็จ
  • ในขณะที่ j + 1 a[j]
    • up :=true และเพิ่ม j ขึ้น 1
  • ขณะขึ้นเป็นจริงและ j + 1 a[j]
    • ลง :=true และเพิ่ม j ขึ้น 1
  • ถ้าขึ้นและลงทั้งสองเป็นจริง ให้ตั้งค่า ret :=max ของ j – i + 1 และ ret ให้ลด j ขึ้น 1
• คืนสินค้า

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

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

อินพุต

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

ผลลัพธ์

5