Kiểm tra mảng con có dạng núi trong C++

Trong bài toán này, chúng ta được cho một mảng số nguyên arr[] và một khoảng [L, R]. Nhiệm vụ là kiểm tra xem mảng con trong khoảng đó có dạng núi hay không.

Ví dụ minh họa

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

Giải thích: Mảng con = {2, 5, 6, 7, 3, 0}. Giá trị trước tăng dần sau đó giảm dần.

Phương pháp giải

Sử dụng mảng phụ để lưu chỉ số của phần tử tăng cuối cùng và giảm đầu tiên cho mỗi vị trí. Sau đó kiểm tra điều kiện núi trong khoảng cho trước.

Ví dụ chương trình

#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 << "Mảng con có dạng núi";
    else
        cout << "Mảng con không có dạng núi";
    return 0;
}

Kết quả

Mảng con có dạng núi