Chương trình Python tìm số tập con lớn hơn giá trị cho trước

Giả sử ta có mảng chứa các số nguyên. Ta tìm tất cả các mảng con liên tiếp (subarrays) từ mảng đã cho và đưa vào danh sách khác. Sau đó, thay thế mỗi mảng con bằng phần tử lớn nhất trong mảng con đó. Có thêm số k, ta phải tìm số mảng con hiện tại lớn hơn k.

Ví dụ: input_array = [5, 6, 7, 8], k = 7, kết quả là 4.

Các mảng con liên tiếp: {5}, {6}, {7}, {8}, {5,6}, {6,7}, {7,8}, {5,6,7}, {6,7,8}, {5,6,7,8}

Thay bằng max: {5}, {6}, {7}, {8}, {6}, {7}, {8}, {7}, {8}, {8}

Có 4 tập con có phần tử > 7.

Giải thuật

1. count := 0, consecutive := 0
2. Với mỗi x trong input_array:
   • Nếu x > k: consecutive := 0
   • Ngược lại: consecutive++, count += consecutive
3. Trả về len(input_array) * (len(input_array) + 1) // 2 - count

Ví dụ

def solve(input_array, k):
    count = 0
    consecutive = 0
    for x in input_array:
        if x > k:
            consecutive = 0
        else:
            consecutive += 1
            count += consecutive
    return len(input_array) * (len(input_array) + 1) // 2 - count

print(solve([5, 6, 7, 8], 7))

Input

[5, 6, 7, 8], 7

Output

4