Tối đa hóa tổng mảng với hoạt động nhất định trong C ++

Mô tả

Có một mảng (2 * n - 1) số nguyên. Ta có thể đổi dấu của chính xác n phần tử trong mảng. Nói cách khác, chúng ta có thể chọn chính xác n phần tử của mảng và nhân mỗi phần tử đó với -1. Tìm tổng lớn nhất của mảng.

Ví dụ

Nếu mảng đầu vào là {-2, 100, -3} thì chúng ta có thể nhận được dấu thay đổi lớn nhất của -2 và -3. Sau khi thay đổi mảng dấu trở thành -

{2, 100, 3} và tổng tối đa của mảng này là 105.

Thuật toán

• Đếm số âm
• Tính tổng của mảng bằng cách lấy các giá trị tuyệt đối của các số.
• Tìm số nhỏ nhất của mảng bằng cách lấy các giá trị tuyệt đối của các số
• Kiểm tra xem có không. của các số âm là lẻ và giá trị của n là chẵn sau đó lấy tổng trừ đi hai lần m và đây sẽ là tổng lớn nhất của mảng khác, giá trị của tổng sẽ là tổng lớn nhất của mảng
• Lặp lại các bước trên (2 * n - 1) lần

Ví dụ

Bây giờ chúng ta hãy xem một ví dụ -

#include <bits/stdc++.h>
using namespace std;
int getMaxSum(int *arr, int n) {
   int negtiveCnt = 0;
   int sum = 0;
   int m = INT_MAX;
   for (int i = 0; i < 2 * n - 1; ++i) {
      if (arr[i] < 0) {
         ++negtiveCnt;
      }
      sum = sum + abs(arr[i]);
      m = min(m, abs(arr[i]));
   }
   if (negtiveCnt % 2 && n % 2 == 0) {
      sum = sum - 2 * m;
      return sum;
   }
   return sum;
}
int main() {
   int arr[] = {-2, 100, -3};
   int n = 2;
   cout << "Maximum sum = " << getMaxSum(arr, n) << endl;
   return 0;
}

Đầu ra

Maximum sum = 105