Tối đa hóa tổng mảng sau khi phủ định K trong C ++

Tuyên bố vấn đề

Cho một mảng kích thước n và một số k. Chúng ta phải sửa đổi một mảng k số lần.

Sửa đổi mảng có nghĩa là trong mỗi thao tác, chúng ta có thể thay thế bất kỳ phần tử nào của mảng arr [i] bằng cách phủ định nó, tức là arr [i] =-arr [i]. Nhiệm vụ là thực hiện thao tác này sao cho sau k phép toán, tổng của một mảng phải là lớn nhất.

Nếu đầu vào arr [] ={7, -3, 5, 4, -1} thì tổng tối đa sẽ là 20

• Phủ định đầu tiên -3. Bây giờ mảng trở thành {7, 3, 5, 4, -1}
• Phủ nhận -1. Bây giờ mảng trở thành {7, 3, 5, 4, 1}

Thuật toán

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

Ví dụ

#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;
}

Đầu ra

Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau &mnus;

Maximum sum = 20