[not solved] 3040. Maximum Number of Operations With the Same Score II | 1709
Why is this thing 1709?
First version is good but TLEs, I think it’s because I am copying new lists every time:
1class Solution:
2 def maxOperations(self, nums: List[int]) -> int:
3 # intuition: backtrack?
4
5 def bt(ops: int, score: int, arr: List[int]) -> int:
6 # print(ops, score, arr)
7 if len(arr) < 2:
8 return ops
9
10 first_two = ops
11 last_two = ops
12 first_last = ops
13
14 if arr[0] + arr[1] == score:
15 first_two = bt(ops + 1, score, arr[2:])
16 if arr[-1] + arr[-2] == score:
17 last_two = bt(ops + 1, score, arr[:-2])
18 if arr[0] + arr[-1] == score:
19 first_last = bt(ops + 1, score, arr[1:-1])
20
21 return max([first_two, last_two, first_last])
22
23 if len(nums) < 2:
24 return 0
25
26 ft = bt(1, nums[0] + nums[1], nums[2:])
27 lt = bt(1, nums[-1] + nums[-2], nums[:-2])
28 fl = bt(1, nums[0] + nums[-1], nums[1:-1])
29 # print(ft, lt, fl)
30
31 return max([ft, lt, fl])
let’s switch to indexes and see:
1class Solution:
2 def maxOperations(self, nums: List[int]) -> int:
3 # intuition: backtracking with l, r pointers
4
5 # you can infer remaining_length from l and r but
6 def bt(
7 num_of_ops: int, score: int, remaining_length: int, l: int, r: int
8 ) -> int:
9 nonlocal nums
10
11 if remaining_length < 2:
12 return num_of_ops
13
14 first_two = num_of_ops
15 last_two = num_of_ops
16 first_last = num_of_ops
17
18 if nums[l] + nums[l + 1] == score:
19 first_two = bt(num_of_ops + 1, score, remaining_length - 2, l + 2, r)
20 if nums[r] + nums[r - 1] == score:
21 last_two = bt(num_of_ops + 1, score, remaining_length - 2, l, r - 2)
22 if nums[l] + nums[r] == score:
23 first_last = bt(
24 num_of_ops + 1, score, remaining_length - 2, l + 1, r - 1
25 )
26
27 return max(first_two, last_two, first_last)
28
29 n = len(nums)
30 return max(
31 bt(1, nums[0] + nums[1], n - 2, 2, n - 1),
32 bt(1, nums[-1] + nums[-2], n - 2, 0, n - 3),
33 bt(1, nums[0] + nums[-1], n - 2, 1, n - 2),
34 )
It still TLEs.
Because the runtime is O(3^(n/2)).
DP is needed for scenarios like this:
given a fixed score: dp[l][r] returns the best possible num_of_ops from here till the end.
This saves time because: i first remove first two then last two, vs i first remove last two then first two, reaches the same solution.
"""
Without memoization, the recursion is a tree:
each state can branch up to 3 ways
so naive worst-case looks like about 3^(n/2) (exponential)
With memoization (fixed score):
each (l, r) state is computed once
number of possible (l, r) pairs is about n*(n+1)/2 → O(n²)
each state does constant work (up to 3 checks/transitions)
So per score: O(n²) time, O(n²) memory.
With 3 scores: still O(n²) overall (just 3×).
"""
1# tbd