2024-07-24: In go, given an array of integers nums, which contains at least two elements. Operations can be performed according to the following rules: select the top two elements to delete, select the last two elements to delete, or select the first and

2024-07-24: In go, given an array of integers nums, which contains at least two elements.

Operations can be performed according to the following rules: select the top two elements to delete, select the last two elements to delete, or select the first and last elements to delete.

The score for each operation is the sum of the deleted elements.

All operation scores need to remain the same after each operation.

The question asks to determine the maximum number of operations that can be performed under these premises.

Eventually the maximum number of operations that can be performed needs to be returned.

Input: nums = [3,2,6,1,4].

Output: 2.

Explanation: We perform the following:

Delete the first two elements and the fraction is 3 + 2 = 5 with nums = [6,1,4].

Delete the last two elements and the fraction is 1 + 4 = 5 with nums = [6].

Perform up to 2 operations.

Answer 2024-07-24:

chatgpt

Title from leetcode3040.

The broad steps are as follows:

1. The program defines amaxOperations function, which is passed an array of integersnums, the function returns the maximum number of operations.

2. InmaxOperations function creates a two-dimensional memo array of the length of the array to be used in the memoized search.

3. Defines an internal helper functionhelper, which implements a dynamic planning problem solving process.

4. Inhelper In the function, the score calculation for each operation is realized by recursion, as well as recording the score of each operation, and finally returning the maximum number of operations.

5. The main operations include the choice of deleting the first two elements, deleting the last two elements, or deleting the first and last elements of the three cases.

6. In the main function, given an example array[3,2,6,1,4], and outputs the maximum number of operations.

Total time complexity:

• Time complexity when defining memo arrays: O(n^2)

• Time complexity of recursive calculation of operation score: O(n^2)

• The overall time complexity is O(n^2)

Total extra space complexity:

• The memo array has an additional space complexity of O(n^2) for memoized search.

• Stack space overhead during recursive calls is not considered.

• The overall extra space complexity is O(n^2).

The full Go code is below:

package main

import (
	"fmt"
)

func maxOperations(nums []int) int {
    n := len(nums)
	memo := make([][]int, n)
	
    helper := func(i, j, target int) int {
        for i := range memo {
            memo[i] = make([]int, n)
            for j := range memo[i] {
                memo[i][j] = -1
            }
        }

        var dfs func(int, int) int
        dfs = func(i, j int) int {
            if i >= j {
                return 0
            }
            if memo[i][j] != -1 {
                return memo[i][j]
            }

            ans := 0
            if nums[i] + nums[i + 1] == target {
                ans = max(ans, 1 + dfs(i + 2, j))
            }
            if nums[j - 1] + nums[j] == target {
                ans = max(ans, 1 + dfs(i, j - 2))
            }
            if nums[i] + nums[j] == target {
                ans = max(ans, 1 + dfs(i + 1, j - 1))
            }
            memo[i][j] = ans
            return ans
        }
        return dfs(i, j)
    }
	
	res := 0
	res = max(res, helper(0, n - 1, nums[0] + nums[n - 1]))
	res = max(res, helper(0, n - 1, nums[0] + nums[1]))
	res = max(res, helper(0, n - 1, nums[n - 2] + nums[n - 1]))
	return res
}

func main() {
	nums:=[]int{3,2,6,1,4}
	(maxOperations(nums))
}