Number of Sub-arrays With Odd Sum LeetCode solution in C++

1
class Solution {
2
 public:
3
  int mod = 1e9 + 7;
4
  int solve(int ind, int n, vector<int> &arr, int req, vector<vector<int>> &dp) {
5
    if (ind == n) return 0;
6
    if (dp[ind][req] != -1) return dp[ind][req];
7
    if (req == 1) {
8
      if (arr[ind] % 2 == 0) {
9
        return dp[ind][req] = solve(ind + 1, n, arr, req, dp);
10
      } else {
11
        return dp[ind][req] = (1 + solve(ind + 1, n, arr, !req, dp)) % mod;
12
      }
13
    } else {
14
      if (arr[ind] % 2 == 0) {
15
        return dp[ind][req] = (1 + solve(ind + 1, n, arr, req, dp)) % mod;
16
      } else {
17
        return dp[ind][req] = solve(ind + 1, n, arr, !req, dp);
18
      }
19
    }
20
  }
21
  int numOfSubarrays(vector<int> &arr) {
22
    int n = arr.size();
23
    vector<vector<int>> dp(n, vector<int>(2, -1));
24
    int count = 0;
25
    for (int i = 0; i < n; i++) {
26
      count = (count + solve(i, n, arr, 1, dp)) % mod;
27
    }
28
    return count;
29
  }
30
};