#include<iostream>
#include<algorithm>
using namespace std;
int n,a[500005],b[500005];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)scanf("%d",&b[i]);
	sort(a+1,a+n+1);
	sort(b+1,b+n+1);
	printf("%d",a[n]+b[n]);
	return 0;
}

📝 题目大意

给定两个长度为 $N$ 的整数数列 $A$ 和 $B$，可以任意选择下标 $i$ 和 $j$（$1 \leq i, j \leq N$），求 $A_i + B_j$ 的最大值。

💡 解题思路

1. 题目分析：$i$ 和 $j$ 的选择是相互独立的——$A_i$ 和 $B_j$ 之间没有任何配对限制，任何一个 $A$ 中的元素都可以与任何一个 $B$ 中的元素相加。因此问题等价于：从 $A$ 中选一个最大值，从 $B$ 中选一个最大值，两者相加即为答案。

2. 算法推导：

   • 朴素思路：枚举所有 $i, j$ 的组合，计算 $A_i + B_j$ 并取最大值，时间复杂度 $O(N^2)$，在 $N \leq 5 \times 10^5$ 的数据范围下不可接受。
   • 优化思路：由于 $\max_{i,j}(A_i + B_j) = \max_i A_i + \max_j B_j$（加法的单调性保证：对于任意 $A_i, B_j$，有 $A_i + B_j \leq \max A + \max B$，而取 $i$ 为 $A$ 中最大值下标、$j$ 为 $B$ 中最大值下标时可取到等号），因此只需分别遍历两个数组，各找出最大值，然后相加即可。
   • 实现方式：用变量 max1 记录 $A$ 的最大值，max2 记录 $B$ 的最大值。初始值设为 $-10^9$（题目中 $|A_i|, |B_j| \leq 10^9$，但元素可能全为负数，所以初始值设为足够小的负数）。遍历 $A$ 时遇到更大的值就更新 max1，遍历 $B$ 时同理更新 max2，最后输出 max1 + max2。

3. 边界与细节：

   • 所有元素均为负数：此时最大值仍为两数组各自的最大值（即绝对值最小的负数）之和，初始值 max1、max2 设为 $-10^9$（或 -1e9）能正确覆盖这种情况。
   • 溢出：|A_i|, |B_j| \leq 10^9，因此最大和为 $2 \times 10^9$，在 32 位有符号整数（约 $2.147 \times 10^9$）范围内，使用 int 类型即可。
   • $N = 1$：直接输出 $A_1 + B_1$，算法依然正确。

⏱️ 复杂度分析

• 时间复杂度：遍历数组 $A$ 一次、数组 $B$ 一次，每次 $O(N)$，总复杂度 $O(N)$。
• 空间复杂度：不需要存储整个数组，仅用几个变量在读入时即时处理，额外空间 $O(1)$。

💻 标准代码 (C++)

#include<bits/stdc++.h>
using namespace std;
int n, a, max1 = -1e9, max2 = -1e9; // max1 记录 A 的最大值，max2 记录 B 的最大值，初始化为足够小的负数
int main()
{
    cin >> n;
    // 读入数组 A，同时找出最大值
    for(int i = 0; i < n; i++)
    {
        cin >> a;
        if(a > max1) max1 = a; // 更新 A 的最大值
    }
    // 读入数组 B，同时找出最大值
    for(int i = 0; i < n; i++)
    {
        cin >> a;
        if(a > max2) max2 = a; // 更新 B 的最大值
    }
    cout << max1 + max2; // 答案即为两数组最大值之和
    return 0;
}