เพิ่มผลรวมของอาร์เรย์สูงสุดหลังจาก K Negations ใน Python

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

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

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

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

• เรียงลำดับอาร์เรย์ A

• สำหรับผมอยู่ในช่วง 0 ถึงความยาวของ A – 1

  • ถ้า A[i] <0 แล้ว A[i] :=- A[i] และลด k ลง 1

  • ถ้า k =0 ให้แยกออกจากลูป

• ถ้า k เป็นคู่ ดังนั้น

  • sp :=A[0]

  • for i :=1 ถึงความยาวของ A – 1

    • ถ้า A[i]> 0 แล้ว sp :=ขั้นต่ำของ 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))

อินพุต

[3,-1,0,2]
3

ผลลัพธ์

6