โปรแกรมหาผลรวมสูงสุดด้วยการ Negate สูงสุด K ครั้งใน Python

ให้ลิสต์ nums และ k สามารถ Negate (คูณ -1) ได้ทุกครั้งที่เลือกสมาชิก ต้องทำครบ k ครั้ง หาผลรวมสูงสุด

ตัวอย่าง: nums=[2,1,-6,-2], k=3 → 9 (Negate -6, -2, 1 → [2,-1,6,2] Sum=9)

ขั้นตอน (Greedy + Sort)

1. เรียง nums จากน้อยไปมาก
2. Negate ตัวเลขติดลบตั้งแต่น้อยที่สุด จนกว่า k=0 หรือหมดตัวติดลบ
3. ถ้า k เหลือเป็นคี่: ลบ 2*min(nums) ออกจากผลรวม (Negate ตัวเล็กที่สุดอีกครั้ง)
4. คืนผลรวม

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

def solve(nums, k):
    n = len(nums)
    if n == 0:
        return 0
    nums.sort()
    for idx in range(n):
        if nums[idx] < 0 and k > 0:
            k -= 1
            nums[idx] *= -1
    if k & 1 == 1:
        return sum(nums) - 2 * min(nums)
    return sum(nums)

nums = [2, 1, -6, -2]
k = 3
print(solve(nums, k))  # Output: 9

อินพุต

[2, 1, -6, -2], 3

เอาต์พุต

9