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, j + 1만큼 i 증가
  • j :=나
  • 아래로 :=거짓, 위로 :=거짓
  • j + 1 a[j]
    동안
    • up :=true이고 j를 1만큼 증가
  • up은 true이고 j + 1 a[j]
    • down :=true이고 j를 1만큼 증가
  • 위쪽과 아래쪽이 모두 true이면 ret :=max of 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