Chương trình tìm người thắng cuộc trong trò chơi mảng bằng Python

Cho mảng arr phần tử duy nhất và số k. Trò chơi: lấy 2 phần tử đầu, so sánh, phần tử lớn hơn thắng và ở vị trí 0, phần tử nhỏ hơn đưa về cuối. Kết thúc khi một giá trị thắng k vòng liên tiếp. Tìm giá trị thắng.

Ví dụ: arr=[1,5,6,3,4,2], k=3 → 6 thắng 3 vòng liên tiếp.

Thuật toán

• l = len(arr), prev = arr[0], count = 0
• Duyệt i từ 1 đến l-1:
  • Nếu prev > arr[i]: count += 1
  • Ngược lại: prev = arr[i]; count = 1
  • Nếu count == k: return prev
• Return prev (phần tử max toàn mảng sẽ thắng vô hạn)

Code Python

def solve(arr, k):
    l = len(arr)
    prev = arr[0]
    count = 0
    for i in range(1, l):
        if prev > arr[i]:
            count += 1
        else:
            prev = arr[i]
            count = 1
        if count == k:
            return prev
    return prev

arr = [1,5,6,3,4,2]
k = 3
print(solve(arr, k))

Input

[1,5,6,3,4,2], 3

Output

6