2321. 拼接数组的最大分数

发表于 分类于 阅读次数： Waline： 本文字数： 820 阅读时长 ≈ 3 分钟

考点

  • 最大子数组和
  • 数学
  • 贪心

思路

一、问题回顾（抽象描述）

给定两个长度相同的整数数组 \[ \text{nums}_1,\ \text{nums}_2 \in \mathbb{Z}^n \] 允许 至多选择一个连续子区间 \([l,r]\)，并将该区间在两个数组中 整体交换。 目标是：交换后，使得 两个数组元素和中的较大者最大化。

形式化目标： \[ \max \Big( \sum \text{nums}_1',\ \sum \text{nums}_2' \Big) \] 其中 \(\text{nums}_1', \text{nums}_2'\) 是交换区间后的数组。

二、直接建模：交换区间带来的“收益”

1. 原始数组和

记： \[ S_1 = \sum_{i=0}^{n-1} \text{nums}_1[i], \quad S_2 = \sum_{i=0}^{n-1} \text{nums}_2[i] \] 若 不交换，答案即为： \[ \max(S_1, S_2) \]

2. 交换区间的影响分析

设交换区间为 \([l, r]\)。

  • 对数组 1：

\[ S_1' = S_1 - \sum_{i=l}^r \text{nums}_1[i] + \sum_{i=l}^r \text{nums}_2[i] \]

  • 对数组 2：

\[ S_2' = S_2 - \sum_{i=l}^r \text{nums}_2[i] + \sum_{i=l}^r \text{nums}_1[i] \]

三、关键化简：差分数组与收益转化

1. 定义差分收益

定义两个“交换收益数组”：

  • nums2 → nums1 的收益

\[ d_1[i] = \text{nums}_2[i] - \text{nums}_1[i] \]

  • nums1 → nums2 的收益

\[ d_2[i] = \text{nums}_1[i] - \text{nums}_2[i] = -d_1[i] \]

2. 交换区间后的新和

  • 若目标是最大化 \(S_1'\)：

\[ S_1' = S_1 + \sum_{i=l}^r d_1[i] \]

  • 若目标是最大化 \(S_2'\)：

\[ S_2' = S_2 + \sum_{i=l}^r d_2[i] \]

3. 问题等价转化

原问题等价于：

在数组 \(d_1\) 和 \(d_2\) 中，分别选择一个 最大子段和，并加到对应的原数组和中，取最大值。

即： \[ \max\Big( S_1 + \max\text{subarray}(d_1),\ S_2 + \max\text{subarray}(d_2) \Big) \]

四、贪心 + DP：最大子段和（Kadane）

1. DP 状态定义

以 \(d_1\) 为例： \[ dp_1[i] = \max(d_1[i],\ dp_1[i-1] + d_1[i]) \] 表示： 以位置 \(i\) 结尾的最大连续子段和

\(d_2\) 同理。

2. 贪心本质

该转移体现的贪心思想是：

  • 若前缀和为负，则直接舍弃
  • 只保留“对后续有正贡献”的区间

这正是经典的 Kadane 算法。

五、整体算法流程

  1. 计算原始数组和 \(S_1, S_2\)
  2. 同时维护：
    • \(u\)：当前 \(d_1\) 的最大子段和（nums2 → nums1）
    • \(v\)：当前 \(d_2\) 的最大子段和（nums1 → nums2）
  3. 遍历数组并动态更新
  4. 每一步尝试更新最终答案

六、时间与空间复杂度

  • 时间复杂度：\(\mathcal{O}(n)\)
  • 空间复杂度：\(\mathcal{O}(1)\)（仅使用常数变量）

七、代码（含逐行注释）

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
class Solution {
public:
    int maximumsSplicedArray(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();

        // pa, pb 分别表示 nums1 和 nums2 的原始总和
        int pa = 0, pb = 0;
        for (int i = 0; i < n; ++i) {
            pa += nums1[i];
            pb += nums2[i];
        }

        // u：当前以 i 结尾的最大子段和（nums2 -> nums1 的收益）
        // v：当前以 i 结尾的最大子段和（nums1 -> nums2 的收益）
        int u = nums2[0] - nums1[0];
        int v = nums1[0] - nums2[0];

        // 初始答案：不交换任何区间
        int res = max(pa, pb);

        for (int i = 1; i < n; ++i) {
            int d1 = nums2[i] - nums1[i]; // 对 nums1 的收益
            int d2 = nums1[i] - nums2[i]; // 对 nums2 的收益

            // Kadane 转移：要么从当前位置重新开始，要么接上前面的区间
            u = max(d1, u + d1);
            v = max(d2, v + d2);

            // 尝试更新答案：
            // u - pb + pa + pb = pa + u
            // v - pa + pa + pb = pb + v
            res = max(res, max(pa + u, pb + v));
        }

        return res;
    }
};