เพิ่มผลรวมอาร์เรย์หลัง K Negations (Maximize Sum Of Array After K Negations) ใน Python

สมมติว่าเรามีอาร์เรย์ A ของจำนวนเต็ม เราต้องแก้ไขอาร์เรย์ดังนี้:

เราสามารถเลือก i และแทนที่ A[i] ด้วย -A[i] และเราจะทำซ้ำกระบวนการนี้ K ครั้ง เราต้องคืนค่าผลรวมที่มากที่สุดของอาร์เรย์หลังจากเปลี่ยนแปลงแบบนี้

ดังนั้น ถ้าอาร์เรย์ A = [4,2,3], และ K = 1 ผลลัพธ์จะเป็น 5 เลือก index 1 อาร์เรย์จะกลายเป็น [4,-2,3]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:

• เรียงลำดับอาร์เรย์ A
• for i ใน range 0 ถึง length of A - 1
  • ถ้า A[i] < 0 แล้ว A[i] := -A[i], และลด k ลง 1
  • ถ้า k = 0 แล้ว break ออกจาก loop
• ถ้า k เป็นเลขคู่ แล้ว
  • sp := A[0]
  • for i := 1 ถึง length of A - 1
    • ถ้า A[i] > 0 แล้ว sp := minimum ของ sp และ A[i]
  • คืนค่าผลรวมของสมาชิก A - (2*sp)
• มิฉะนั้น คืนค่าผลรวมของสมาชิก A

ตัวอย่าง (Python)

ลองดูการทำงานต่อไปนี้เพื่อเข้าใจดีขึ้น:

class Solution(object):
    def largestSumAfterKNegations(self, A, K):
        A.sort()
        for i in range(len(A)):
            if A[i] < 0:
                A[i] = -A[i]
                K -= 1
            if K == 0:
                break
        if K % 2:
            smallest_positive = A[0]
            for i in range(1, len(A)):
                if A[i] >= 0:
                    smallest_positive = min(smallest_positive, A[i])
            return sum(A) - (2 * smallest_positive)
        else:
            return sum(A)

ob1 = Solution()
print(ob1.largestSumAfterKNegations([3, -1, 0, 2], 3))

Input

[3,-1,0,2] 3

Output

6