nikunjsoni

1340

Jun 29th, 2021
125
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     int dp[1001] = {};
  4.     int dfs(vector<int>& arr, int i, int d, int res = 1) {
  5.         if (dp[i]) return dp[i];
  6.         for (auto j = i + 1; j <= min(i + d, (int)arr.size() - 1) && arr[j] < arr[i]; ++j)
  7.             res = max(res, 1 + dfs(arr, j, d));
  8.         for (auto j = i - 1; j >= max(0, i - d) && arr[j] < arr[i]; --j)
  9.             res = max(res, 1 + dfs(arr, j, d));
  10.         return dp[i] = res;
  11.     }
  12.     int maxJumps(vector<int>& arr, int d, int res = 1) {
  13.         for (auto i = 0; i < arr.size(); ++i)
  14.             res = max(res, dfs(arr, i, d));
  15.         return res;
  16.     }
  17. };
RAW Paste Data