Implementasi Range Maximum Queries

range_maximum_queries.py

# Misalkan sudah ada index (M) dan datanya (A) seperti ini
A = [8, 6, 3, 8, 4, 7, 1, 6, 9]

M = [
    [0, 0, 0, 0, 0, 0, 0, 0, 8],
    [0, 1, 1, 3, 3, 3, 3, 3, 8],
    [0, 1, 2, 3, 3, 3, 3, 3, 8],
    [0, 3, 3, 3, 3, 3, 3, 3, 8],
    [0, 3, 3, 3, 4, 5, 5, 5, 8],
    [0, 3, 3, 3, 5, 5, 5, 5, 8],
    [0, 3, 3, 3, 5, 5, 6, 7, 8],
    [0, 3, 3, 3, 5, 5, 7, 7, 8],
    [8, 8, 8, 8, 8, 8, 8, 8, 8],
]


def range_maximum_queries(k: int, M_indices: list[tuple[int, int]]):
    """
    Mengembalikan top-k element dari A dengan memanfaatkan index M

    Parameters
    ----------
    k = jumlah top element. ASUMSI: k <= panjang subarray A yang diminta

    M_indices = list berisi index-index yang harus diproses untuk mendapatkan
    top-k element ke-i. Ini sesuai ide di slides. Setiap index inklusif kedua ujung
    """
    top_k_elements: list[int] = []
    for i in range(k):
        curr_A_max_element = -1
        curr_A_max_index = -1

        # 1. Cari untuk setiap index, mana elemen dan index terbesar sebagai top element ke-i
        for M_index in M_indices:
            A_max_index = M[M_index[0]][M_index[1]]
            A_max_element = A[A_max_index]
            if A_max_element > curr_A_max_element:
                curr_A_max_element = A_max_element
                curr_A_max_index = A_max_index
        print(f"Top {i} element: {curr_A_max_element}")
        top_k_elements.append(curr_A_max_element)

        # 2. Update M_indices agar mengandung index-index yang harus dicari untuk top element ke-i+1
        new_M_indices = []
        for index in M_indices:
            if curr_A_max_index in range(index[0], index[1] + 1):
                if (curr_A_max_index - 1) >= index[0]:
                    new_M_indices.append((index[0], curr_A_max_index - 1))
                if (curr_A_max_index + 1) <= index[1]:
                    new_M_indices.append((curr_A_max_index + 1, index[1]))
            else:
                new_M_indices.append(index)
        M_indices = new_M_indices
    return top_k_elements


# Misalkan kita cari top-3 elements di A[1:5]
print(range_maximum_queries(3, [(1, 5)]))  # [8, 7, 6]