समस्या कथन
आकार 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