Tìm hiệu lớn nhất giữa ước nhỏ hơn bên trái và bên phải trong Python

Cho mảng số nguyên, tìm hiệu tuyệt đối lớn nhất giữa phần tử nhỏ hơn gần nhất bên trái và bên phải của mỗi phần tử. Nếu không có phần tử nhỏ hơn bên nào, coi giá trị đó là 0.

Ví dụ: A = [3, 5, 9, 8, 8, 10, 4] → Left smaller: [0, 3, 5, 5, 5, 8, 3], Right smaller: [0, 4, 8, 4, 4, 4, 0] → Max |L-R| = 4 (tại 8).

Thuật toán dùng Stack

1. Hàm left_small_element(A, temp): duyệt trái sang phải, dùng stack đơn điệu tăng. Với mỗi A[i], pop stack cho đến khi top < A[i], thì top là left smaller. Push A[i].
2. Gọi hàm cho mảng gốc (lấy left smaller) và mảng đảo ngược (lấy right smaller).
3. Tính max |left[i] - right[n-1-i]|.

Ví dụ code

def left_small_element(A, temp):
    n = len(A)
    stack = []
    for i in range(n):
        while stack and stack[-1] >= A[i]:
            stack.pop()
        temp[i] = stack[-1] if stack else 0
        stack.append(A[i])

def find_maximum_difference(A):
    n = len(A)
    left = [0] * n
    right = [0] * n
    left_small_element(A, left)
    left_small_element(A[::-1], right)
    res = -1
    for i in range(n):
        res = max(res, abs(left[i] - right[n - 1 - i]))
    return res

A = [3, 5, 9, 8, 8, 10, 4]
print(find_maximum_difference(A))

Input

[3, 5, 9, 8, 8, 10, 4]

Output

4