Dãy núi dài nhất trong mảng C++ (Longest Mountain in Array)

Tìm độ dài subarray liên tiếp dài nhất tạo thành "núi": tăng dần rồi giảm dần, độ dài ≥ 3.

Định nghĩa núi

Subarray B: B[0] < B[1] < ... < B[i] > B[i+1] > ... > B[B.length-1] với 0 < i < B.length-1.

Ví dụ

Input - [2,1,4,7,3,2,5] Output - 5

Giải thích - Núi lớn nhất: [1,4,7,3,2] độ dài 5.

Phương pháp tiếp cận (Two Pointers)

• Duyệt i từ 0, dùng j mở rộng
• Phase 1: Tăng (up=true) cho đến khi không tăng nữa
• Phase 2: Giảm (down=true) cho đến khi không giảm nữa
• Nếu up && down: cập nhật max length = j-i+1
• Nhảy i = j+1 (hoặc j nếu đã giảm)

Ví dụ code C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int longestMountain(vector<int>& a) {
        int ret = 0, n = a.size(), j;
        for (int i = 0; i < n; i = j + 1) {
            j = i;
            bool down = false, 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;
    }
};

int main() {
    vector<int> v = {2,1,4,7,3,2,5};
    Solution ob;
    cout << ob.longestMountain(v);
    return 0;
}

Kết quả

5