Chương trình tìm số chunk tối đa để sắp xếp mảng trong Python

Cho mảng nums. Chia mảng thành các partition, sắp xếp từng partition riêng lẻ, nối lại được mảng toàn cục đã sắp xếp. Tìm số partition tối đa.

Ví dụ: [3,2,4,5,5] → output = 4 (partition: [3,2], [4], [5], [5]).

Giải thuật (So sánh prefix sorted)

• real = sorted(nums).
• Duyệt p1=0, p2=1...: lấy nums[p1:p2], sort → tmp. So sánh tmp với real[p1:p2].
• Nếu khớp → tìm được 1 partition, p1=p2, p2++, count++.
• Không khớp → p2++ (mở rộng partition).
• Dừng khi p1 == n.

Code Python

def solve(nums):
    real = sorted(nums)
    p1, p2, c = 0, 1, 0
    while True:
        flag = True
        tmp = sorted(nums[p1:p2])
        for j in range(len(tmp)):
            if tmp[j] != real[p1 + j]:
                flag = False
                p2 += 1
                break
        if flag:
            p1, p2 = p2, p2 + 1
            c += 1
        if p1 == len(nums) or p2 > len(nums):
            return c

nums = [3, 2, 4, 5, 5]
print(solve(nums))  # 4

Đầu vào / Đầu ra

Input: [3,2,4,5,5]
Output: 4