两数组不同索引元素最大和求解：O(n)复杂度动态规划实现

给定两个长度均为n的整数数组A和B，要求从A中选一个元素A[i]、从B中选一个元素B[j]，且i≠j，求这两个元素的最大和。

为什么简单贪心行不通？ #

直接取A的最大值和B的最大值的思路会直接失效——如果这两个最大值的索引相同，就无法满足i≠j的要求。而仅依赖「取A最大值+B次大值」或「A次大值+B最大值」的简化贪心逻辑，在存在多个等值最大值的场景下也可能出现判断疏漏，因此需要一种更可靠的O(n)级解法。

解法：前缀+后缀最大值递推（动态规划思路） #

核心思路 #

我们可以将问题拆解为：对每个索引i，计算A[i]加上B数组中除B[i]外的最大值，最终取所有计算结果中的最大值。要高效得到每个i对应的B数组非自身最大值，可通过递推生成前缀最大值数组和后缀最大值数组——这本质是动态规划的状态转移过程：每个位置的状态依赖于之前/之后的状态结果。

具体步骤 #

1. 生成B数组的前缀最大值数组：
   • prefix_b[i] 表示B数组从0到i-1位置的最大值，初始时prefix_b[0] = -∞（i=0时无前置元素）
   • 遍历i从1到n-1，递推公式：prefix_b[i] = max(prefix_b[i-1], B[i-1])
2. 生成B数组的后缀最大值数组：
   • suffix_b[i] 表示B数组从i+1到n-1位置的最大值，初始时suffix_b[n-1] = -∞（i=n-1时无后置元素）
   • 遍历i从n-2到0，递推公式：suffix_b[i] = max(suffix_b[i+1], B[i+1])
3. 计算全局最大和：遍历每个i，计算A[i] + max(prefix_b[i], suffix_b[i])，记录所有结果中的最大值。

Python 代码示例 #

def max_sum_diff_indices(A, B):
    n = len(A)
    if n < 2:
        return -1  # 元素数量不足时无法满足i≠j的要求
    
    # 计算B的前缀最大值数组
    prefix_b = [float('-inf')] * n
    for i in range(1, n):
        prefix_b[i] = max(prefix_b[i-1], B[i-1])
    
    # 计算B的后缀最大值数组
    suffix_b = [float('-inf')] * n
    for i in range(n-2, -1, -1):
        suffix_b[i] = max(suffix_b[i+1], B[i+1])
    
    max_total = float('-inf')
    for i in range(n):
        current_max_b = max(prefix_b[i], suffix_b[i])
        current_sum = A[i] + current_max_b
        if current_sum > max_total:
            max_total = current_sum
    return max_total

空间优化版本（O(1) 空间） #

如果对空间复杂度有更高要求，也可以通过记录数组的前两大元素及其索引，枚举所有合法组合得到最大值：

def max_sum_diff_indices_optimized(A, B):
    n = len(A)
    if n < 2:
        return -1
    
    # 找出A数组前两大元素及对应索引
    a1, a2 = float('-inf'), float('-inf')
    idx_a1, idx_a2 = -1, -1
    for i in range(n):
        if A[i] > a1:
            a2, idx_a2 = a1, idx_a1
            a1, idx_a1 = A[i], i
        elif A[i] > a2:
            a2, idx_a2 = A[i], i
    
    # 找出B数组前两大元素及对应索引
    b1, b2 = float('-inf'), float('-inf')
    idx_b1, idx_b2 = -1, -1
    for i in range(n):
        if B[i] > b1:
            b2, idx_b2 = b1, idx_b1
            b1, idx_b1 = B[i], i
        elif B[i] > b2:
            b2, idx_b2 = B[i], i
    
    # 枚举所有合法的前两大元素组合
    candidates = []
    if idx_a1 != idx_b1:
        candidates.append(a1 + b1)
    if idx_a1 != idx_b2:
        candidates.append(a1 + b2)
    if idx_a2 != idx_b1:
        candidates.append(a2 + b1)
    if idx_a2 != idx_b2:
        candidates.append(a2 + b2)
    return max(candidates)

内容的提问来源于stack exchange，提问作者Tomek Swiecki