Trong bài toán này, chúng ta được cung cấp một mảng các số nguyên arr [] và một dải ô. Nhiệm vụ của chúng ta là tìm xem một mảng con có ở dạng núi hay không .
Hãy lấy một ví dụ để hiểu vấn đề,
Input : arr[] = {1, 4, 2, 5, 6, 7, 3, 0}, range = [2, 7]
Output : Yes Giải thích -
Subarray of range = {2, 5, 6, 7, 3, 0}
The values first increase and then decrease. Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là sử dụng các mảng phụ. Chúng tôi sẽ tìm chỉ số của phần tử cuối cùng đang tăng cho mỗi phần tử của mảng và làm tương tự đối với các giá trị giảm dần. Sau đó, kiểm tra ngọn núi trong khoảng thời gian nhất định.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi
#include <iostream>
using namespace std;
int 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;
int 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;
} Đầu ra
The subarray is in mountain form