Jump Game V LeetCode solution in Rust

1
use std::cell::*;
2
use std::char::*;
3
use std::cmp::*;
4
use std::collections::hash_map::*;
5
use std::collections::*;
6
use std::iter::*;
7
use std::mem::*;
8
use std::ops::*;
9
use std::*;
10

11
fn dfs(pos: usize, arr: &Vec<i32>, d: usize, count: &mut Vec<i32>) -> i32 {
12
  // check if we can jump
13
  let mut can_jump_left = true;
14
  let mut can_jump_right = true;
15
  if pos == 0 || arr[pos - 1] >= arr[pos] {
16
    can_jump_left = false;
17
  }
18
  if pos == arr.len() - 1 || arr[pos + 1] >= arr[pos] {
19
    can_jump_right = false;
20
  }
21

22
  let mut ret = 0;
23

24
  if can_jump_left {
25
    for i in 1..min(pos, d) + 1 {
26
      let i = pos - i;
27
      if arr[i] >= arr[pos] {
28
        break;
29
      }
30

31
      if count[i] == -1 {
32
        let m = dfs(i, arr, d, count);
33
        ret = max(ret, m + 1);
34
      } else {
35
        ret = max(ret, count[i] + 1);
36
      }
37
    }
38
  }
39

40
  if can_jump_right {
41
    for i in 1..min(arr.len() - pos - 1, d) + 1 {
42
      let i = pos + i;
43
      if arr[i] >= arr[pos] {
44
        break;
45
      }
46

47
      if count[i] == -1 {
48
        let m = dfs(i, arr, d, count);
49
        ret = max(ret, m + 1);
50
      } else {
51
        ret = max(ret, count[i] + 1);
52
      }
53
    }
54
  }
55

56
  count[pos] = ret;
57
  ret
58
}
59

60
impl Solution {
61
  pub fn max_jumps(arr: Vec<i32>, d: i32) -> i32 {
62
    let mut ans = 0;
63
    let mut count = vec![-1; arr.len()];
64

65
    for i in 0..arr.len() {
66
      count.fill(-1);
67
      ans = max(ans, dfs(i, &arr, d as usize, &mut count));
68
    }
69

70
    ans + 1
71
  }
72
}