โปรแกรมหาค่าน้อยที่สุดที่ต้องแทรกหน้ารายการเพื่อให้ Prefix Sums เป็นบวกทั้งหมดใน Python

การหาค่าน้อยที่สุดที่แทรกหน้ารายการเพื่อ Prefix Sums เป็นบวก

กำหนดรายการ nums หาค่า x > 0 น้อยที่สุด ที่นำ x ไปวางหน้า nums แล้ว prefix sums ของรายการใหม่เป็นบวกทั้งหมด

อัลกอริทึม

1. แทรก 0 เข้าไปหน้า nums (เพื่อคำนวณ prefix sums ได้ง่าย)
2. คำนวณ prefix sums แบบสะสม
3. หาค่าต่ำสุดของ prefix sums (min_val)
4. คำตอบ = 1 - min_val (ทำให้ prefix sums น้อยที่สุดกลายเป็น 1)

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

def solve(nums):
    nums.insert(0, 0)
    for i in range(1, len(nums)):
        nums[i] += nums[i - 1]
    return 1 - min(nums)

nums = [3, -6, 4, 3]
print(solve(nums))

ผลลัพธ์

4

คำอธิบาย

nums = [3, -6, 4, 3] → prefix sums = [3, -3, 1, 4] ค่าต่ำสุด = -3

แทรก 4 → [4, 3, -6, 4, 3] → prefix sums = [4, 7, 1, 5, 8] ทุกค่าบวก