2026-09-11：下标覆盖处的最大总和。用go语言，有一个长度为 n 的整数数组 nums，还有一个长度同样为 n 的二进制字符串 s。 对于每个位

2026-09-11：下标覆盖处的最大总和。用go语言，有一个长度为 n 的整数数组 nums，还有一个长度同样为 n 的二进制字符串 s。

对于每个位置 i：

• • 如果 s[i] 是 '1'，表示这个位置一开始有一个标记；

• • 如果 s[i] 是 '0'，表示这个位置一开始没有标记。

你可以进行任意多次这样的操作：

• • 选一个当前在位置 i 的标记，其中 i 必须大于 0；

• • 并且这个标记以前从来没有被移动过；

• • 然后把它从位置 i 移动到位置 i - 1。

所有移动结束后，只要某个位置上有标记，就说明这个位置被覆盖了。

要求返回一个整数，表示在采取最优移动方案后，所有被覆盖位置上的 nums 数值之和最大是多少。

1 <= n == nums.length == s.length <= 100000。

1 <= nums[i] <= 100000。

s[i] 要么是 '0'，要么是 '1'。

输入： nums = [9,2,6,1], s = "0101"。

输出： 15。

解释：

初始时，下标 1 和 3 包含标记。

将标记从下标 3 移动到下标 2。

将标记从下标 1 移动到下标 0。

被覆盖的下标为 [0, 2]，所以总值为 nums[0] + nums[2]

题目来自力扣3952。

这个函数用的是一次从左到右的动态规划扫描。核心观察是：每个初始标记都在s[i] == '1'的位置，并且每个标记最多只能向左移动一格，也就是从i到i-1。所以一个位置i是否被覆盖，只可能来自两种来源：

1. 1. 它自己有初始标记，并且选择不移动；

2. 2. 它右边相邻位置i+1有初始标记，并且那个标记选择左移到i。

因此，问题可以看成：每个'1'标记选择覆盖自己，或者覆盖左边相邻位置，使最终被覆盖位置的nums总和最大。

代码中维护了两个状态值：

• •f0：可以理解为“已经确定下来的最优覆盖总和”，并且没有把当前位置预留给右边的标记来覆盖；

• •f1：可以理解为“暂时预支了当前位置被覆盖”的最优总和，也就是假设当前位置会被右边的'1'左移过来覆盖，先把它加上，等待后面遇到'1'时兑现。

具体过程如下：

1. 1. 初始化f0 = 0，f1 = 0。

2. 2. 从左到右遍历每个下标i，记当前数值为x = nums[i]。

3. 3. 如果s[i] == '0'：

• • 这个位置自己没有初始标记，不能靠自己覆盖。

• • 它唯一可能被覆盖的方式，是右边相邻位置i+1的标记左移过来。

• • 所以已经确定的状态f0不变；

• • 同时从f0出发，预支当前位置被覆盖，得到新的f1 = f0 + x。

• • 旧的f1表示之前某个预支状态，但当前是'0'，无法用当前标记兑现，所以被新的预支状态取代。

4. 如果s[i] == '1'：

• • 当前位置有一个初始标记。

• • 这个标记有两种选择：

1. 1. 左移到i-1：如果之前对i-1有预支状态，那么现在可以兑现它，总和保持为旧的f1；

2. 2. 留在i：覆盖当前位置，总和从f0增加x，即f0 + x。

• 因此新的确定状态取两者最大值：f0 = max(f0 + x, f1)。

• 然后f1 += x，表示在预支状态下，当前位置也可以被覆盖，继续把这个预支状态向后传递。

5. 遍历结束后，所有位置都处理完了，不可能再有右边的标记来兑现预支状态，所以最终答案就是确定状态f0。

用题目例子nums = [9,2,6,1]，s = "0101"模拟：

• • 初始：f0 = 0，f1 = 0

• •i = 0，s[0] = '0'，x = 9：

• • •f1 = f0 + 9 = 9

  • •f0仍为0

  • • 表示预支下标 0 被右边标记覆盖。

• •i = 1，s[1] = '1'，x = 2：

• • •f0 = max(f0 + 2, f1) = max(2, 9) = 9

  • •f1 = f1 + 2 = 11

  • • 表示确定下标 0 被覆盖，总和为 9。

• •i = 2，s[2] = '0'，x = 6：

• • •f1 = f0 + 6 = 15

  • •f0仍为9

  • • 表示在确定下标 0 覆盖的基础上，预支下标 2 被右边标记覆盖。

• •i = 3，s[3] = '1'，x = 1：

• • •f0 = max(f0 + 1, f1) = max(10, 15) = 15

  • •f1 = f1 + 1 = 16

  • • 最终确定状态为 15。

对应最优操作：
把下标 3 的标记移动到下标 2，把下标 1 的标记移动到下标 0。
最终覆盖下标[0, 2]，总和为nums[0] + nums[2] = 9 + 6 = 15。

时间复杂度：只遍历一次数组和字符串，每个位置做常数次操作，所以是O(n)。
额外空间复杂度：只使用了f0、f1等常数个变量，没有额外数组或递归栈，所以是O(1)。

Go完整代码如下：

package main

 import (
    "fmt"
)

 func maxTotal(nums []int, s string) int64 {
    f0, f1 := 0, 0
    for i, x := range nums {
        if s[i] == '0' {
            f1 = f0 + x
        } else {
            f0 = max(f0+x, f1)
            f1 += x
        }
    }
    return int64(f0)
}

 func main() {
    nums := []int{9, 2, 6, 1}
    s := "0101"
    result := maxTotal(nums, s)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

 def max_total(nums, s):
    f0, f1 = 0, 0
    for i, x in enumerate(nums):
        if s[i] == '0':
            f1 = f0 + x
        else:
            f0 = max(f0 + x, f1)
            f1 += x
    return f0

 if __name__ == "__main__":
    nums = [9, 2, 6, 1]
    s = "0101"
    result = max_total(nums, s)
    print(result)

C++完整代码如下：

  

  

  


 long long maxTotal(const std::vector& nums, const std::string& s) {
    long long f0 = 0, f1 = 0;
    for (size_t i = 0; i < nums.size(); ++i) {
        int x = nums[i];
        if (s[i] == '0') {
            f1 = f0 + x;
        } else {
            f0 = std::max(f0 + x, f1);
            f1 += x;
        }
    }
    return f0;
}

 int main() {
    std::vector nums = {9, 2, 6, 1};
    std::string s = "0101";
    long long result = maxTotal(nums, s);
    std::cout << result << std::endl;
    return 0;
}

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。