विवरण
(2 * n - 1) पूर्णांकों का एक ऐरे है। हम ऐरे में ठीक n तत्वों का चिन्ह बदल सकते हैं। दूसरे शब्दों में, हम ठीक n ऐरे तत्वों का चयन कर सकते हैं, और उनमें से प्रत्येक को -1 से गुणा कर सकते हैं। ऐरे का अधिकतम योग ज्ञात करें।
उदाहरण
यदि इनपुट ऐरे है {-2, 100, -3} तो हम -2 और -3 का चिन्ह बदलकर अधिकतम प्राप्त कर सकते हैं। चिन्ह बदलने के बाद ऐरे बन जाता है:
{2, 100, 3} और इस ऐरे का अधिकतम योग 105 है।
एल्गोरिदम
- ऋणात्मक संख्याओं की गिनती करें।
- संख्याओं के निरपेक्ष मान लेकर ऐरे का योग निकालें।
- संख्याओं के निरपेक्ष मान लेकर ऐरे की न्यूनतम संख्या ढूंढें।
- जांचें कि क्या ऋणात्मक संख्याओं की संख्या विषम है और n का मान सम है तो योग में से दो गुना m घटाएं और यह ऐरे का अधिकतम योग होगा अन्यथा, योग का मान ऐरे का अधिकतम योग होगा।
- उपरोक्त चरणों को (2 * n - 1) बार दोहराएं।
उदाहरण
#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;
}
आउटपुट
Maximum sum = 105
