maximum-number-of-operations-with-the-same-score-ii.cpp

// Time:  O(n^2)
// Space: O(n^2)

// memoization
class Solution {
public:
    int maxOperations(vector<int>& nums) {
        const function<int (int, int, int, vector<vector<int>>&)> memoization = [&](int left, int right, int target, vector<vector<int>>& lookup) {
            if (!(right - left + 1 >= 2)) {
                return 0;
            }
            if (lookup[left][right] == -1) {
                lookup[left][right] = max({nums[left] + nums[left + 1]   == target ? 1 + memoization(left + 2, right - 0, target, lookup) : 0,
                                           nums[left] + nums[right]      == target ? 1 + memoization(left + 1, right - 1, target, lookup) : 0,
                                           nums[right - 1] + nums[right] == target ? 1 + memoization(left + 0, right - 2, target, lookup) : 0});
            }
            return lookup[left][right];
        };

        int result = 0;
        for (const auto& target : unordered_set<int>{nums[0] + nums[1], nums[0] + nums[size(nums) - 1], nums[size(nums) - 2] + nums[size(nums) - 1]}) {
            vector<vector<int>> lookup(size(nums), vector<int>(size(nums), -1));
            result = max(result, memoization(0, size(nums) - 1, target, lookup));
        }
        return result;
    }
};