寻找满足i<j<k、A[i]<A[j]<A[k]且B三元组和最大的高效解法

核心思路 #

放弃暴力三重循环，转而固定中间元素j：对每个j，我们只需要找到左边所有i<j且A[i]<A[j]里的最大B[i]，再找到右边所有k>j且A[k]>A[j]里的最大B[k]，三者之和的最大值就是我们要的结果。这种方法把时间复杂度从O(n³)降到O(n²)，实现简单且性能提升显著。

具体实现步骤 #

1. 预处理左侧最大B值数组

   • 创建数组left_max，长度与A、B一致，初始值设为负无穷（表示当前j左侧无符合条件的i）。
   • 遍历每个j（从1到n-1）：
     • 遍历i从0到j-1：
       • 若A[i] < A[j]且B[i] > left_max[j]，更新left_max[j] = B[i]。

2. 预处理右侧最大B值数组

   • 创建数组right_max，长度与A、B一致，初始值设为负无穷。
   • 遍历每个j（从n-2到0）：
     • 遍历k从j+1到n-1：
       • 若A[k] > A[j]且B[k] > right_max[j]，更新right_max[j] = B[k]。

3. 计算最大三元组和

   • 初始化max_sum为负无穷。
   • 遍历每个j：
     • 若left_max[j]和right_max[j]均不为负无穷（说明存在符合条件的i和k）：
       • 计算当前和B[j] + left_max[j] + right_max[j]，若大于max_sum则更新max_sum。
   • 最终，若max_sum仍为负无穷，返回-1（表示无符合条件的三元组）；否则返回max_sum。

进阶优化：O(nlogn)方案（适用于超大数组） #

如果数组规模极大，O(n²)仍不够用，可以借助有序数据结构+二分查找进一步优化：

• 左侧处理：从左到右遍历，维护一个按A值排序的列表，同时记录前缀最大B值。对每个j，用二分查找快速定位所有A[i]<A[j]的最大B值。
• 右侧处理：从右到左遍历，维护一个按A值排序的列表，同时记录后缀最大B值。对每个j，用二分查找快速定位所有A[k]>A[j]的最大B值。
  该方案时间复杂度为O(nlogn)，但实现复杂度略高，适合极端场景。

代码示例（Python） #

def max_triple_sum(A, B):
    n = len(A)
    if n < 3:
        return -1  # 数组长度不足3，无符合条件的三元组
    
    left_max = [-float('inf')] * n
    for j in range(1, n):
        current_max = -float('inf')
        for i in range(j):
            if A[i] < A[j] and B[i] > current_max:
                current_max = B[i]
        left_max[j] = current_max
    
    right_max = [-float('inf')] * n
    for j in range(n-2, -1, -1):
        current_max = -float('inf')
        for k in range(j+1, n):
            if A[k] > A[j] and B[k] > current_max:
                current_max = B[k]
        right_max[j] = current_max
    
    max_sum = -float('inf')
    for j in range(n):
        if left_max[j] != -float('inf') and right_max[j] != -float('inf'):
            total = B[j] + left_max[j] + right_max[j]
            if total > max_sum:
                max_sum = total
    
    return max_sum if max_sum != -float('inf') else -1

内容的提问来源于stack exchange，提问作者Nehal Birla