Chương trình tìm số lượng phân đoạn tối đa để mảng được sắp xếp sau khi sắp xếp từng đoạn bằng Python

Cho danh sách nums. Phân hoạch thành các đoạn, sắp xếp từng đoạn riêng lẻ. Tìm số đoạn tối đa sao cho sau khi sắp xếp các đoạn thì toàn bộ mảng được sắp xếp.

Ví dụ: nums=[4,3,2,1,7,5] → 2 (đoạn [4,3,2,1] và [7,5]).

Giải thuật

• Duyệt song song nums và sorted(nums).
• Giữ tổng tiền tố main_sum của nums và sorted_sum của mảng đã sắp xếp.
• Khi main_sum == sorted_sum: có thể cắt đoạn tại đây, tăng đếm.
• Trả về số đoạn.

Ví dụ minh họa

class Solution:
    def solve(self, nums):
        count = 0
        main_sum = sorted_sum = 0
        for x, y in zip(nums, sorted(nums)):
            main_sum += x
            sorted_sum += y
            if main_sum == sorted_sum:
                count += 1
        return count

ob = Solution()
nums = [4, 3, 2, 1, 7, 5]
print(ob.solve(nums))

Đầu vào

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

Đầu ra

2