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
31
32
33
34
35
36
37
| func maxOperations(nums []int) int {
n := len(nums)
cache := make([][]int, n)
for i := range cache {
cache[i] = make([]int, n)
for j := range cache[i] {
cache[i][j] = -1
}
}
return max(dfs(nums, nums[0]+nums[1], 0, 2, n-1, cache),
max(dfs(nums, nums[n-2]+nums[n-1], 0, 0, n-3, cache),
dfs(nums, nums[0]+nums[n-1], 0, 1, n-2, cache))) + 1
}
func dfs(nums []int, sum, count, left, right int, cache [][]int) int {
if left >= right {
return 0
}
if cache[left][right] != -1 {
return cache[left][right]
}
curCount := 0
// 前两个元素
if sum == nums[left]+nums[left+1] {
curCount = max(curCount, 1+dfs(nums, sum, count, left+2, right, cache))
}
// 最后两个元素
if sum == nums[right]+nums[right-1] {
curCount = max(curCount, 1+dfs(nums, sum, count, left, right-2, cache))
}
// 前后两个元素
if sum == nums[left]+nums[right] {
curCount = max(curCount, 1+dfs(nums, sum, count, left+1, right-1, cache))
}
cache[left][right] = count + curCount
return cache[left][right]
}
|
