โปรแกรมหาจำนวน Chunk สูงสุดเพื่อทำให้ Array เรียงลำดับใน Python

ปัญหา

อาร์เรย์ nums แบ่งเป็น Partitions เรียงแต่ละ Partition แยกกัน แล้ว Concat ได้ Array เรียงลำดับ หาจำนวน Partitions สูงสุด

ตัวอย่าง

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

Partitions: [3,2], [4], [5], [5] → Sorted: [2,3], [4], [5], [5] → Concat: [2,3,4,5,5] ✓

อัลกอริทึม (Greedy + Sorted Comparison)

1. Real = Sorted(nums)
2. Two Pointers p1, p2 กำหนดช่วง Partition ปัจจุบัน
3. Sort Subarray nums[p1:p2] เปรียบเทียบกับ Real[p1:p2]
4. ถ้าตรงกัน → Partition นี้ OK, p1=p2, p2++, Count++
5. ถ้าไม่ตรง → p2++ (ขยาย Partition)
6. จน p1 == n หรือ p2 > n

ตัวอย่างโค้ด

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

ความซับซ้อน

• Time: O(n² log n) - Sort แต่ละ Partition
• Space: O(n)
• Optimization: ใช้ Frequency Count / Multiset Comparison แทน Sort → O(n log n)