โปรแกรมแบ่งอาร์เรย์เป็นสองช่วงที่ไม่ทับซ้อนใน Python

สมมติว่ามีอาร์เรย์ nums ต้องแบ่งเป็น left และ right ที่:

• ทุกค่าใน left ≤ ทุกค่าใน right
• ทั้งสองไม่ว่าง
• left มีขนาดน้อยที่สุด

คืนความยาวของ left

ตัวอย่าง: nums = [5,0,3,8,6] ผลลัพธ์ 3 (left=[5,0,3], right=[8,6])

วิธีแก้ปัญหา

1. mx := None, temp := None, nmx := None, temp2 := 0
2. วน i ใน nums:
   • ถ้า mx is None: เริ่มต้นค่า
   • ถ้า i >= mx: เพิ่ม temp2, อัปเดต nmx
   • มิฉะนั้น: temp = temp2, temp2 += 1, mx = nmx
3. คืน temp + 1

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

def solve(nums):
    mx = None
    temp = None
    nmx = None
    temp2 = 0
    for i in nums:
        if mx is None:
            mx = i
            nmx = i
            temp = temp2
            temp2 += 1
            continue
        if i >= mx:
            temp2 += 1
            if i > nmx:
                nmx = i
            continue
        else:
            temp = temp2
            temp2 += 1
            mx = nmx
            continue
    return temp + 1

nums = [5,0,3,8,6]
print(solve(nums))

อินพุต

[5,0,3,8,6]

เอาต์พุต

3