समस्या कथन
आकार 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. वर्तमान ऑपरेशन के लिए ऐरे में न्यूनतम तत्व arr[i] को -arr[i] से बदलें। 2. एक बार न्यूनतम तत्व 0 बन जाने पर, हमें और बदलाव करने की आवश्यकता नहीं है। इस तरह हम K ऑपरेशन के बाद ऐरे का योग अधिकतम कर सकते हैं।
उदाहरण
#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;
}
आउटपुट
Maximum sum = 20
