周赛353

2769. 找出最大的可达成数字

解题思路：

很显然 $num + 2t$ 就是可达成最大数字

示例代码：

func theMaximumAchievableX(num int, t int) int {
    return num + t*2
}

2770. 达到末尾下标所需的最大跳跃次数

解题思路：

从后往前跳跃，定义 $dfs(index)$ 表示从 $index$ 跳到 0 的最大跳跃次数

用「枚举选哪个」来思考：

枚举 $i$，如果满足 $-target \leq nums[index] - nums[i] \leq target$，那么：

$$dfs(index) = dfs(i) +1$$

取所有情况的最大值，就是 $dfs(i)$

如果没有满足条件的 $i$，那么 $dfs(i) = -\infty$

递归边界：$dfs(0) = 0$

递归入口：$dfs(n-1)$，如果答案为负数则返回 -1

示例代码：

func maximumJumps(nums []int, target int) int {
    n := len(nums)
    var dfs func(int) int
    memo := make([]int, n)
    for i := 0; i < n; i++ {
        memo[i] = -1
    }
    dfs = func(index int) int {
        if index == 0 {
            return 0
        }

        if memo[index] == -1 {
            memo[index] = math.MinInt
            for i := index - 1; i >= 0; i-- {
                if -target <= nums[index]-nums[i] && nums[index]-nums[i] <= target {
                    memo[index] = max(memo[index], dfs(i)+1)
                }
            }

        }
        return memo[index]
    }
    res := dfs(n - 1)
    if res < 0 {
        return -1
    }
    return res
}

2771. 构造最长非递减子数组

解题思路：

将 $nums1,nums2$ 放入数组 $nums$ 中方便后续遍历

定义 $dfs(i,j)$ 表示以 $nums_j[i]$ 结尾的最长非递归子数组长度（$j$ 为 $nums$ 数组下标）。用「枚举选哪个」来思考：

• 如果 $nums_1[i-1] \leq nums_j[i]$，那么下一步选 $nums_1[i-1]$， 有 $dfs(j,j) = dfs(i-1, 0)+1$
• 如果 $nums_2[i-1] \leq nums_j[i]$，那么下一步选 $nums_2[i-1]$， 有 $dfs(j,j) = dfs(i-1, 1)+1$
• 如果二者都不成立，$dfs(i,j) = 1$ (子数组长度为1)

上述情况去最大值，就是 $dfs(i,j)$

递归边界：$dfs(0)=1$

递归入口：$dfs(i,j)$。遍历所有 $i,j$ 取 $dfs(i,j)$ 的最大值，即为答案

示例代码：

func maxNonDecreasingLength(nums1 []int, nums2 []int) int {
    n := len(nums1)
    nums := [2][]int{nums1, nums2}
    memo := make([][2]int, n)
    for i := range memo {
        memo[i] = [2]int{-1, -1}
    }
    var dfs func(int, int) int // i,j 以下标i结束的nums[j]结尾的最长非递归子数组长度

    dfs = func(i int, j int) int {
        if i == 0 {
            return 1
        }

        if memo[i][j] == -1 {
            memo[i][j] = 1
            if nums1[i-1] <= nums[j][i] {
                memo[i][j] = dfs(i-1, 0) + 1
            }
            if nums2[i-1] <= nums[j][i] {
                memo[i][j] = max(dfs(i-1, 1)+1, memo[i][j])
            }
        }

        return memo[i][j]
    }

    var res int
    for j := 0; j < 2; j++ {
        for i := 0; i < n; i++ {
            res = max(res, dfs(i, j))
        }
    }
    return res
}

翻译成递推

func maxNonDecreasingLength(nums1 []int, nums2 []int) int {
    n := len(nums1)
    nums := [2][]int{nums1, nums2}
    dp := make([][2]int, n)
    dp[0] = [2]int{1, 1}

    var res = 1
    for i := 1; i < n; i++ {
        dp[i] = [2]int{1, 1}
        for j := 0; j < 2; j++ {
            if nums1[i-1] <= nums[j][i] {
                dp[i][j] = dp[i-1][0] + 1
            }
            if nums2[i-1] <= nums[j][i] {
                dp[i][j] = max(dp[i-1][1]+1, dp[i][j])
            }
        }
        res = max(res, max(dp[i][0], dp[i][1]))
    }

    return res
}

因为 $dp[i]$ 只用到了 $dp[i-1]$， 所以可以进一步优化：

func maxNonDecreasingLength(nums1 []int, nums2 []int) int {
    n := len(nums1)
    dp0, dp1 := 1, 1

    var res = 1
    for i := 1; i < n; i++ {
        j0, j1 := 1, 1
        // for j := 0; j < 2; j++ {
        if nums1[i-1] <= nums1[i] {
            // dp[i][j] = dp[i-1][0] + 1
            j0 = dp0 + 1
        }
        if nums2[i-1] <= nums1[i] {
            // dp[i][j] = max(dp[i-1][1]+1, dp[i][j])
            j0 = max(dp1+1, j0)
        }
        if nums1[i-1] <= nums2[i] {
            // dp[i][j] = dp[i-1][0] + 1
            j1 = dp0 + 1
        }
        if nums2[i-1] <= nums2[i] {
            // dp[i][j] = max(dp[i-1][1]+1, dp[i][j])
            j1 = max(dp1+1, j1)
        }
        dp0, dp1 = j0, j1
        // }
        res = max(res, max(dp0, dp1))
    }

    return res
}

2772. 使数组中的所有元素都等于零

解题思路：

如果 $nums[i] > 0$，就必须要把 $nums[i]$ 到 $nums[i+k-1]$ 都减去 $nums[i]$，然后再继续查看 $nums[i+1]$，重复上述操作

设差分数组 $d$，那么把 $nums[i]$ 到 $nums[i+k-1]$ 都减去 1 等价于把 $d[i]$ 减1，$d[i+k]$ 加 1，注意子数组长度为 $k$，所以当 $i+k \leq n$ 时，才能执行上述操作。

遍历数组是，用遍历 $sumD$ 累计差分值，遍历到 $nums[i]$ 时，$nums[i]+sumD$ 就是实际 $nums[i]$ 的值

分类讨论：

• 如果 $nums[i] < 0$，根据题意只能减，返回 false
• 如果 $nums[i] =0$，不需要再操作，直接跳过
• 如果 $nums[i] > 0$：
  • 如果 $i+k > n$，无法执行操作，$nums[i]$ 无法变成 0， 返回 false
  • 如果 $i+k < n$，修改差分数组，继续遍历下一个数

如果没有在遍历途中返回 false，则表示可以全部改为 0，返回 true

示例代码：

func checkArray(nums []int, k int) bool {
    n := len(nums)
    d := make([]int, n+1)
    sumD := 0
    for i, num := range nums {
        sumD += d[i]
        num += sumD
        if num == 0 { // 已经为0,无需操作
            continue
        }
        if num < 0 || i+k > n { // 无法继续操作
            return false
        }
        sumD -= num // d[i] -= num
        d[i+k] += num
    }
    return true
}