求解数组中的最大正差值索引问题

先咱们把问题的定义再明确下，避免理解偏差：

给定数组A，「正差值索引」指的是：对于满足i<j的索引对(i,j)，在区间[i,j]内所有符合k<l且A[k]<A[l]的元素对(k,l)的总数。我们的目标是找出所有这类(i,j)中，这个总数的最大值。

下面我给你从简单到高效的几种解法，你可以根据数据量来选择：

解法一：暴力枚举（适合小数据量） #

这是最直观的思路——遍历所有可能的i<j区间，逐个统计每个区间内的正序对数量，最后记录最大值。

步骤： #

• 初始化max_count为0，用来保存当前找到的最大正序对数量
• 外层循环遍历每个起始索引i（从0到n-2，因为j必须大于i）
• 内层循环遍历每个结束索引j（从i+1到n-1）
• 对每个区间[i,j]，再嵌套两层循环遍历所有k<l的元素对，统计A[k]<A[l]的次数
• 每次统计完一个区间后，更新max_count

代码示例（Python）： #

def max_positive_diff_index(arr):
    n = len(arr)
    max_count = 0
    for i in range(n):
        for j in range(i + 1, n):
            current_count = 0
            # 统计当前区间[i,j]内的正序对
            for k in range(i, j):
                for l in range(k + 1, j + 1):
                    if arr[k] < arr[l]:
                        current_count += 1
            if current_count > max_count:
                max_count = current_count
    return max_count

# 处理输入输出
T = int(input())
for _ in range(T):
    N = int(input())
    A = list(map(int, input().split()))
    print(max_positive_diff_index(A))

⚠️ 注意：这个方法的时间复杂度是O(n⁴)，当数组长度n超过20时，运行速度会变得非常慢，只适合测试小样本。

解法二：优化版暴力枚举（O(n³)） #

我们可以对区间统计的过程做个小优化：当我们把区间从[i,j-1]扩展到[i,j]时，不需要重新遍历整个区间，只需要统计i到j-1中比A[j]小的元素数量，把这个数加到之前的统计结果里就行。

步骤： #

• 初始化max_count为0
• 外层循环遍历起始索引i
• 对每个i，初始化current_count为0，然后遍历j从i+1到n-1：
  • 统计i到j-1中比A[j]小的元素数量，加到current_count上
  • 比较并更新max_count

代码示例（Python）： #

def max_positive_diff_index(arr):
    n = len(arr)
    max_count = 0
    for i in range(n):
        current_count = 0
        for j in range(i + 1, n):
            # 只统计新增的j对应的正序对
            cnt = 0
            for k in range(i, j):
                if arr[k] < arr[j]:
                    cnt += 1
            current_count += cnt
            if current_count > max_count:
                max_count = current_count
    return max_count

# 输入输出处理
T = int(input())
for _ in range(T):
    N = int(input())
    A = list(map(int, input().split()))
    print(max_positive_diff_index(A))

这个方法把时间复杂度降到了O(n³)，比暴力法快了不少，但对于n>100的情况还是会有点吃力。

解法三：分治法（O(n log n)，适合大数据量） #

这个思路借鉴了归并排序中统计逆序对的方法，我们可以用分治法在高效计算正序对的同时，找出最大的区间正序对数量。

核心逻辑是：数组的最大正序对区间要么在左半部分，要么在右半部分，要么是横跨左右的区间。我们递归计算这三个部分的最大值，最终取三者中的最大者。

步骤： #

1. 将数组分成左右两个子数组
2. 递归计算左子数组的最大正序对数量，以及左子数组的总正序对数量
3. 递归计算右子数组的最大正序对数量，以及右子数组的总正序对数量
4. 计算横跨左右的区间的正序对数量（即左子数组元素小于右子数组元素的所有(k,l)对）
5. 横跨区间的总正序对数量 = 左子数组总正序对 + 右子数组总正序对 + 跨左右的正序对数量
6. 当前数组的最大正序对数量 = max(左子数组最大, 右子数组最大, 横跨区间总正序对)

代码示例（Python）： #

def merge_and_count(arr, temp, low, mid, high):
    i = low
    j = mid + 1
    k = low
    cross_count = 0

    # 归并过程中统计跨左右的正序对数量
    while i <= mid and j <= high:
        if arr[i] < arr[j]:
            temp[k] = arr[i]
            # 此时j到high的所有元素都比arr[i]大，所以新增(high - j + 1)个正序对
            cross_count += (high - j + 1)
            i += 1
        else:
            temp[k] = arr[j]
            j += 1
        k += 1

    # 处理剩余元素
    while i <= mid:
        temp[k] = arr[i]
        i += 1
        k += 1
    while j <= high:
        temp[k] = arr[j]
        j += 1
        k += 1

    # 把临时数组的内容复制回原数组
    for idx in range(low, high + 1):
        arr[idx] = temp[idx]

    return cross_count

def divide_and_conquer(arr, temp, low, high):
    max_count = 0
    total_count = 0
    if low < high:
        mid = (low + high) // 2
        # 递归处理左右子数组，返回最大正序对数量和总正序对数量
        left_max, left_total = divide_and_conquer(arr, temp, low, mid)
        right_max, right_total = divide_and_conquer(arr, temp, mid + 1, high)
        # 计算跨左右的正序对数量
        cross_count = merge_and_count(arr, temp, low, mid, high)
        # 整个区间的总正序对数量
        total_count = left_total + right_total + cross_count
        # 更新当前的最大正序对数量
        max_count = max(left_max, right_max, total_count)
    return max_count, total_count

def max_positive_diff_index(arr):
    n = len(arr)
    if n < 2:
        return 0
    temp = [0] * n
    # 传入数组的副本，避免修改原数组
    max_count, _ = divide_and_conquer(arr.copy(), temp, 0, n - 1)
    return max_count

# 输入输出处理
T = int(input())
for _ in range(T):
    N = int(input())
    A = list(map(int, input().split()))
    print(max_positive_diff_index(A))

这个方法的时间复杂度是O(n log n)，即使数组长度达到10^5也能高效处理。

测试示例验证 #

比如输入：

1
4
1 3 2 4

所有区间的正序对数量分别是：

• [0,1]：1
• [0,2]：2
• [0,3]：5
• [1,2]：0
• [1,3]：2
• [2,3]：1
  最大值是5，用上面的代码可以得到正确结果。

内容的提问来源于stack exchange，提问作者Sandeep Thaker