หาภูเขาที่ยาวที่สุดในอาร์เรย์ (Longest Mountain in Array) ใน C++

Subarray เรียกว่า "ภูเขา" (mountain) ถ้า:

• ความยาว ≥ 3
• มีจุดสูงสุด (peak) ที่เพิ่มขึ้นอย่างเคร่งครัดถึงจุดนั้น แล้วลดลงอย่างเคร่งครัดหลังจุดนั้น

ตัวอย่าง

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

คำอธิบาย − ภูเขาที่ยาวที่สุด: [1,4,7,3,2] ความยาว 5

แนวทางการแก้ปัญหา (Two Pointers)

• วนหาจุดเริ่มต้นของภูเขา (ขึ้นก่อน)
• ขยับ j ไปข้างหน้าขณะขึ้น (up = true)
• ต่อขยับ j ขณะลง (down = true)
• ถ้ามีทั้ง up และ down → อัปเดตคำตอบ max(j-i+1)
• ข้ามไปจุดสิ้นสุดของภูเขานี้ (i = j+1)

ตัวอย่างโค้ด C++

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

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

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

ผลลัพธ์

5