C++에서 K 부정 후 배열 합계 최대화

문제 설명

크기가 n이고 숫자가 k인 배열이 주어집니다. 배열을 k번 수정해야 합니다.

배열 수정은 각 작업에서 배열 요소 arr[i]를 무효화하여 대체할 수 있음을 의미합니다(예:arr[i] =-arr[i]). 작업은 k 연산 후에 배열의 합이 최대가 되어야 하는 방식으로 이 연산을 수행하는 것입니다.

입력 arr[] ={7, -3, 5, 4, -1}이면 최대 합계는 20이 됩니다.

• 첫 번째 부정 -3. 이제 배열은 {7, 3, 5, 4, -1}이 됩니다.
• -1을 부정합니다. 이제 배열은 {7, 3, 5, 4, 1}
이 됩니다.

알고리즘

1. Replace the minimum element arr[i] in array by -arr[i] for current operation
2. Once minimum element becomes 0, we don’t need to make any more changes. In this way we can make sum of array maximum after K operations

예시

#include <bits/stdc++.h>
using namespace std;
int getMaxSum(int *arr, int n, int k){
   for (int i = 1; i <= k; ++i) {
      int minValue = INT_MAX;
      int index = -1;
      for (int j = 0; j < n; ++j) {
         if (arr[j] < minValue) {
            minValue = arr[j];
            index = j;
         }
      }
      if (minValue == 0) {
         break;
      }
      arr[index] = -arr[index];
   }
   int sum = 0;
   for (int i = 0; i < n; ++i) {
      sum = sum + arr[i];
   }
   return sum;
}
int main(){
   int arr[] = {7, -3, 5, 4, -1};
   int n = sizeof(arr) / sizeof(arr[0]);
   int k = 2;
   cout << "Maximum sum = " << getMaxSum(arr, n, k) << endl;
   return 0;
}

출력

위의 프로그램을 컴파일하고 실행할 때. 다음 출력 &mnus;

Maximum sum = 20