मान लीजिए हमारे पास arr नामक पूर्णांकों की एक सरणी और एक पूर्णांक d है। एक चरण में हम इंडेक्स i से कूद सकते हैं:
i + x जहां: i + x < n और x की सीमा 1 से d है।
i - x जहां: i - x >= 0 और x की सीमा 1 से d है।
यहां n सरणी का आकार है। इसके अलावा, हम केवल इंडेक्स i से इंडेक्स j पर कूद सकते हैं जब arr[i] > arr[j] और i और j के बीच के सभी इंडेक्स k के लिए arr[i] > arr[k] हो। हम सरणी के किसी भी इंडेक्स से कूदना शुरू कर सकते हैं। हमें अधिकतम इंडेक्स की संख्या ज्ञात करनी है जिन्हें हम देख सकते हैं।
यदि इनपुट d = 2 और ऊंचाईयां हैं -

तो आउटपुट 4 होगा, हम इंडेक्स 10 से शुरू कर सकते हैं। हम इंडेक्स 10 -> 8 -> 6 -> 7 पर कूद सकते हैं। यदि हम इंडेक्स 6 से शुरू करते हैं तो हम केवल इंडेक्स 7 पर कूद सकते हैं। हम इंडेक्स 5 पर नहीं कूद सकते क्योंकि 13 > 9। हम इंडेक्स 4 पर नहीं कूद सकते क्योंकि इंडेक्स 5, इंडेक्स 4 और 6 के बीच है और 13 > 9। और हम इंडेक्स 3 से इंडेक्स 2 या इंडेक्स 1 पर भी नहीं कूद सकते।
हल करने के चरण
एक सरणी dp परिभाषित करें
solve() फ़ंक्शन परिभाषित करें जो सरणी arr, idx, d लेता है
यदि dp[idx] != -1 तो dp[idx] लौटाएं
ret := 1, n := arr का आकार
दाएं ओर (idx+1 से idx+d तक) जाएं: यदि arr[i] >= arr[idx] तो ब्रेक करें, अन्यथा ret = max(ret, 1 + solve(arr, i, d))
बाएं ओर (idx-1 से idx-d तक) जाएं: यदि arr[i] >= arr[idx] तो ब्रेक करें, अन्यथा ret = max(ret, 1 + solve(arr, i, d))
dp[idx] := ret, ret लौटाएं
मुख्य विधि से: सभी इंडेक्स के लिए solve कॉल करें और अधिकतम लौटाएं
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<int> dp;
int solve(vector<int>& arr, int idx, int d) {
if (dp[idx] != -1) return dp[idx];
int ret = 1;
int n = arr.size();
for (int i = idx + 1; i < n; i++) {
if (i > idx + d) break;
if (arr[i] >= arr[idx]) break;
ret = max(ret, 1 + solve(arr, i, d));
}
for (int i = idx - 1; i >= 0; i--) {
if (i < idx - d) break;
if (arr[i] >= arr[idx]) break;
ret = max(ret, 1 + solve(arr, i, d));
}
return dp[idx] = ret;
}
int maxJumps(vector<int>& arr, int d) {
int n = arr.size();
dp = vector<int>(n, -1);
int ret = 1;
for (int i = 0; i < n; i++) {
ret = max(ret, solve(arr, i, d));
}
return ret;
}
};
int main() {
Solution ob;
vector<int> v = {6,4,14,6,8,13,9,7,10,6,12};
cout << (ob.maxJumps(v, 2));
return 0;
}
इनपुट
{6,4,14,6,8,13,9,7,10,6,12}, 2
आउटपुट
4