Chúng ta được cung cấp với một mảng các số nguyên dương và âm và một số K. Nhiệm vụ là tìm tổng lớn nhất của mảng sau khi K thay đổi trong các phần tử của nó. Thao tác thay đổi đơn ở đây sẽ nhân phần tử đơn lẻ với -1.
Phương pháp được sử dụng sẽ là chuyển đổi mọi số âm thành số dương. Nếu có N số âm thì chúng ta sẽ sắp xếp mảng -
-
Nếu N
-
Bây giờ nếu K-N là chẵn thì đối với các phép toán K-N còn lại, việc thay đổi các dấu hiệu sẽ không có tác dụng, không làm gì cả.
-
Nếu K-N là số lẻ thì đối với các phép toán K-N còn lại thay đổi dấu của số nhỏ nhất (sẽ trở thành số âm) nhưng tổng tổng thể sẽ là lớn nhất.
Hoặc
Nếu N> K thì đổi dấu thành K số âm rồi cộng mảng. Tổng sẽ là tối đa.
Đầu vào
Arr[]= { 0,-2,6,4,8,2,-3 } K=4 Đầu ra
Maximum array sum is : 25
Giải thích - 4 thay đổi trong các phần tử là
1. 0,2,6,4,8,2,-3 -2 changed to 2 2. 0,2,6,4,8,2,3 -3 changed to 3 3. 0,-2,6,4,8,2,3 2 changed to -2 4. 0,2,6,4,8,2,3 -2 changed to 2 Maximum sum is 25
Đầu vào
Arr[]= { -1,-2,-3,-4,-5,-6,-7 } K=4 Đầu ra
Maximum array sum is : 16
Giải thích - 4 thay đổi trong các phần tử là
1. -1,-2,-3,-4,-5,-6,7 -7 changed to 7 2. -1,-2,-3,-4,-5,6,7 -6 changed to 6 3. -1,-2,-3,-4,5,6,7 -5 changed to 5 4. -1,-2,-3,4,5,6,7 -4 changed to 4 Maximum sum is 16
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
-
Mảng số nguyên Arr [] được sử dụng để lưu trữ các số nguyên.
-
Số nguyên 'size' lưu trữ độ dài của mảng và K được khởi tạo.
-
Hàm returnSum (int arr [], int n, int k) nhận một mảng, kích thước của nó và k làm đầu vào và trả về tổng lớn nhất của các phần tử của nó sau đúng k phép toán.
-
Trước hết, chúng ta sẽ sắp xếp mảng bằng cách sử dụng sort (arr, arr + n)
-
Bây giờ chúng ta sẽ áp dụng phép toán arr [i] * - 1 cho tất cả các phần tử phủ định cho đến khi đạt đến chỉ mục cuối cùng hoặc k trở thành 0.
-
Nếu k nhỏ hơn số phần tử âm, thì bước trên sẽ thay đổi k -ve phần tử.
-
Nếu k lớn hơn và giá trị còn lại của k sẽ được kiểm tra xem nó là lẻ hay chẵn.
-
Nếu k còn lại là số lẻ thì chúng ta sẽ thay đổi giá trị của phần tử nhỏ nhất bằng cách áp dụng phép toán arr [i] * - 1 một lần, trong đó arr [i] được tìm thấy ít nhất. (nhân với -1 lần lẻ cũng giống như thực hiện một lần)
-
Nếu k còn lại chẵn thì arr [i] * - 1 sẽ không có hiệu lực. Không làm gì cả.
-
Tính tổng của toàn mảng và trả về kết quả.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
int returnSum(int arr[], int n, int k){
// Sort the array elements
sort(arr, arr + n);
// Change signs of the negative elements
// starting from the smallest
//this loop will change the sign of -ve elements
//for each k one -ve element is turned positive
for(i=0;i<n;i++)
if(k>0 && arr[i]<0){
arr[i]=arr[i]*-1;
k--;
}
//if k is non zero and odd change sign of minimum element
//once as it is same as changing its sign odd times
if (k % 2 == 1) {
int min = arr[0];
int pos=0; //index of minimum element
for (i = 1; i < n; i++)
if (arr[i]<min){
min = arr[i];
pos=i;
}
arr[pos] *= -1;
}
int sum = 0;
for (int i = 0; i < n; i++)
sum += arr[i];
return sum;
}
int main(){
int Arr[] = { -3, 4, -3, 6, 8 };
int size =5;
int K = 4;
cout <<"Maximum array sum that can be obtained after exactly k changes"
returnSum(Arr, size, K) << endl;
return 0;
} Đầu ra
Maximum array sum that can be obtained after exactly k changes : 24