C ++中数组中的最长山峰

如果以下属性成立，则考虑（A的）任何（连续）子数组B称为山峰-

• B的大小> = 3

• 存在一些0 <i <B.length-1，使得B [0] <B [1] <... B [i-1] <B [i]> B [i + 1]> ...> B [B.length-1]

假设我们有一个整数数组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

• down：= true并将j增加1

• up：= true并将j增加1

• j：=我

• 下：=假，上：=假

• 而j + 1 <n和a [j + 1]> a [j]

• 而up为true且j +1 <n和a [j +1]> a [j]

• 如果上下都正确，则设置ret：= j – i + 1的最大值，然后将j减1

• 返回ret。

让我们看下面的实现以更好地理解-

示例

#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