A[i] <= A[j]约束下求j-i最大值的优化数组算法

def max_distance(A):
    n = len(A)
    if n < 2:
        return 0
    
    max_dist = 0
    min_val = A[0]
    
    for j in range(1, n):
        if A[j] >= min_val:
            max_dist = max(max_dist, j - A.index(min_val))
        else:
            min_val = A[j]
    
    return max_dist

# 示例
A = [3, 5, 4, 2, 6, 1]
print(max_distance(A))  # 输出: 4

def max_distance_dp(A):
    n = len(A)
    if n < 2:
        return 0
    
    left_min = [0] * n
    right_max = [0] * n
    
    left_min[0] = A[0]
    for i in range(1, n):
        left_min[i] = min(left_min[i-1], A[i])
    
    right_max[n-1] = A[n-1]
    for i in range(n-2, -1, -1):
        right_max[i] = max(right_max[i+1], A[i])
    
    max_dist = 0
    i, j = 0, 0
    while i < n and j < n:
        if left_min[i] <= right_max[j]:
            max_dist = max(max_dist, j - i)
            j += 1
        else:
            i += 1
    
    return max_dist

# 示例
A = [3, 5, 4, 2, 6, 1]
print(max_distance_dp(A))  # 输出: 4