Python에서 K 부정 후 배열의 합 최대화

정수 배열 A가 있다고 가정하면 다음과 같이 배열을 수정해야 합니다. -

우리는 i를 선택하고 A[i]를 -A[i]로 바꿀 수 있으며 이 과정을 K번 반복합니다. 이런 식으로 배열을 변경한 후 배열의 가능한 가장 큰 합계를 반환해야 합니다.

따라서 배열 A =[4,2,3]이고 K =1이면 출력은 5가 됩니다. 따라서 인덱스 1을 선택하면 배열은 [4,-2,3]

이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

배열 A
정렬
범위 0에서 A – 1까지의 i에 대해
- 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
요소의 합을 반환합니다.

예제(파이썬)

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

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