Skip to content

Maximum Number of Operations With the Same Score II⚓︎

Link

Solution⚓︎

See reference (Chinese).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    int maxOperations(vector<int>& nums) {
        int n = nums.size();
        int memo[n][n];

        auto helper = [&](int i, int j, int target) -> int {
            memset(memo, -1, sizeof(memo));

            function<int(int, int)> dfs = [&](int i, int j) -> int {
                if (i >= j) return 0;
                int& res = memo[i][j];
                if (res != -1) return res;
                res = 0;
                if (nums[i] + nums[i + 1] == target) res = max(res, dfs(i + 2, j) + 1);
                if (nums[j - 1] + nums[j] == target) res = max(res, dfs(i, j - 2) + 1);
                if (nums[i] + nums[j] == target) res = max(res, dfs(i + 1, j - 1) + 1);
                return res;
            };

            return dfs(i, j);
        };

        int res1 = helper(2, n - 1, nums[0] + nums[1]);
        int res2 = helper(0, n - 3, nums[n - 2] + nums[n - 1]);
        int res3 = helper(1, n - 2, nums[0] + nums[n - 1]);

        return max({res1, res2, res3}) + 1;
    }
};
  • Time complexity: \(O(n^2)\);
  • Space complexity: \(O(n^2)\).