ตรวจสอบว่า Subarray เป็นรูปแบบภูเขาหรือไม่ใน C++

ในปัญหานี้ เราได้รับอาร์เรย์ของจำนวนเต็มและช่วง (range) งานของเราคือการตรวจสอบว่า subarray ในช่วงนั้นเป็นรูปแบบภูเขาหรือไม่ (ค่าเพิ่มขึ้นแล้วลดลง)

ตัวอย่างเพื่อเข้าใจปัญหา

Input: arr[] = {1, 4, 2, 5, 6, 7, 3, 0}, range = [2, 7] Output: Yes

Subarray = {2, 5, 6, 7, 3, 0} ค่าเพิ่มขึ้นถึง 7 แล้วลดลง

วิธีการแก้ปัญหา

ใช้ array ช่วยเก็บ index ของ element ที่เพิ่มขึ้นล่าสุด (left[]) และ element ที่ลดลงล่าสุด (right[]) สำหรับแต่ละตำแหน่ง แล้วตรวจสอบว่า right[L] >= left[R] หรือไม่

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

#include <iostream>
using namespace std;

void processArray(int arr[], int N, int left[], int right[]) {
    left[0] = 0;
    int increasingValR = 0;
    for (int i = 1; i < N; i++) {
        if (arr[i] > arr[i - 1]) increasingValR = i;
        left[i] = increasingValR;
    }
    right[N - 1] = N - 1;
    int decreasingValL = N - 1;
    for (int i = N - 2; i >= 0; i--) {
        if (arr[i] > arr[i + 1]) decreasingValL = i;
        right[i] = decreasingValL;
    }
}

bool isMountainSubArray(int arr[], int left[], int right[], int L, int R) {
    return (right[L] >= left[R]);
}

int main() {
    int arr[] = {2, 3, 2, 4, 4, 6, 3, 2};
    int N = sizeof(arr) / sizeof(int);
    int left[N], right[N];
    processArray(arr, N, left, right);
    int L = 0, R = 2;
    if (isMountainSubArray(arr, left, right, L, R))
        cout << "The subarray is in mountain form";
    else
        cout << "The subarray is not in mountain form";
    return 0;
}

ผลลัพธ์

The subarray is in mountain form