Maximum Alternating Subsequence Sum LeetCode solution in C++

1
class Solution {
2
 public:
3
  long long dp[2][100001];
4
  long long util(int i, vector<int> &nums, bool isPos) {
5
    if (i >= nums.size()) return 0;
6
    if (dp[isPos][i] != -1) return dp[isPos][i];
7
    long long curr = (isPos ? nums[i] : -1 * nums[i]);
8
    return dp[isPos][i] = max(curr + util(i + 1, nums, !isPos), util(i + 1, nums, isPos));
9
  }
10
  long long maxAlternatingSum(vector<int> &nums) {
11
    memset(dp, -1, sizeof(dp));
12
    return util(0, nums, true);
13
  }
14
};