Check if There is a Valid Partition For The Array LeetCode solution in C++

1
class Solution {
2
 public:
3
  int solve(int i, vector<int> &nums, vector<int> &dp) {
4
    if (i == nums.size()) return 1;
5
    if (dp[i] != -1) return dp[i];
6

7
    int ans = 0;
8
    if (i + 1 < nums.size() and nums[i] == nums[i + 1]) ans = max(ans, solve(i + 2, nums, dp));
9
    if (i + 2 < nums.size()) {
10
      if (nums[i] == nums[i + 1] && nums[i + 1] == nums[i + 2])
11
        ans = max(ans, solve(i + 3, nums, dp));
12
      else if (abs(nums[i] - nums[i + 1]) == 1 and abs(nums[i + 1] - nums[i + 2]) == 1)
13
        ans = max(ans, solve(i + 3, nums, dp));
14
    }
15

16
    return dp[i] = ans;
17
  }
18
  bool validPartition(vector<int> &nums) {
19
    vector<int> dp(nums.size() + 1, -1);
20
    return solve(0, nums, dp);
21
  }
22
};