Python - Tìm dãy con tăng độ dài 3 trong thời gian tuyến tính

Giả sử chúng ta có mảng N số, chúng ta phải kiểm tra xem có tồn tại 3 phần tử b[i] < b[j] < b[k] với i < j < k trong thời gian tuyến tính O(n). Nếu có nhiều bộ ba như vậy, in ra một trong số chúng.

Ví dụ, nếu đầu vào là [13,12,11,6,7,3,31], thì đầu ra là [6,7,31].

Giải pháp:

• n = len(A), maximum = n-1, minimum = 0
• smaller = mảng size 10000 fill 0; smaller[0] = -1
• for i=1..n-1: nếu A[i] <= A[minimum]: minimum=i; smaller[i]=-1; else smaller[i]=minimum
• greater = mảng size 10000 fill 0; greater[n-1] = -1
• for i=n-2..0: nếu A[i] >= A[maximum]: maximum=i; greater[i]=-1; else greater[i]=maximum
• for i=0..n-1: nếu smaller[i]!=-1 và greater[i]!=-1: return A[smaller[i]], A[i], A[greater[i]]
• Trả về "Nothing"

Ví dụ

def find_inc_seq(A):
    n = len(A)
    maximum = n-1
    minimum = 0
    smaller = [0]*10000
    smaller[0] = -1
    for i in range(1, n):
        if (A[i] <= A[minimum]):
            minimum = i
            smaller[i] = -1
        else:
            smaller[i] = minimum
    greater = [0]*10000
    greater[n-1] = -1
    for i in range(n-2, -1, -1):
        if (A[i] >= A[maximum]):
            maximum = i
            greater[i] = -1
        else:
            greater[i] = maximum
    for i in range(0, n):
        if smaller[i] != -1 and greater[i] != -1:
            return A[smaller[i]], A[i], A[greater[i]]
    return "Nothing"

arr = [13, 12, 11, 6, 7, 3, 31]
print(find_inc_seq(arr))

Đầu vào

[13, 12, 11, 6, 7, 3, 31]

Đầu ra

(6, 7, 31)