पता लगाएं कि सी ++ में एक सबरे पहाड़ के रूप में है या नहीं

इस समस्या में, हमें पूर्णांकों की एक सरणी arr[] और एक श्रेणी दी जाती है। हमारा काम पता लगाना है कि कोई उप-सरणी पर्वत के रूप में है या नहीं ।

समस्या को समझने के लिए एक उदाहरण लेते हैं,

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

स्पष्टीकरण -

Subarray of range = {2, 5, 6, 7, 3, 0}
The values first increase and then decrease.

समाधान दृष्टिकोण

अतिरिक्त सरणियों का उपयोग करके समस्या का एक सरल समाधान है। हम अंतिम तत्व का सूचकांक पाएंगे जो सरणी के प्रत्येक तत्व के लिए बढ़ रहा है और घटते मूल्यों के लिए भी ऐसा ही करें। फिर दिए गए समय में पर्वत की जाँच करें।

उदाहरण

हमारे समाधान की कार्यप्रणाली को दर्शाने के लिए कार्यक्रम

#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;
}

आउटपुट

The subarray is in mountain form