हमें सकारात्मक और नकारात्मक पूर्णांकों की एक सरणी और एक संख्या K के साथ दिया गया है। कार्य इसके तत्वों में K परिवर्तन के बाद सरणी का अधिकतम योग ज्ञात करना है। यहां सिंगल चेंज ऑपरेशन सिंगल एलिमेंट को -1 से गुणा करता है।
उपयोग किया जाने वाला दृष्टिकोण प्रत्येक ऋणात्मक संख्या को धनात्मक में परिवर्तित करना होगा। अगर एन नेगेटिव नंबर हैं तो इसके लिए हम ऐरे को सॉर्ट करेंगे -
-
यदि N
-
अब यदि K-N सम है तो शेष K-N संचालन के लिए संकेतों को बदलने का कोई प्रभाव नहीं पड़ेगा, कुछ न करें।
-
यदि K-N विषम है तो शेष K-N संक्रियाओं के लिए न्यूनतम संख्या का चिह्न बदल दें (जो ऋणात्मक हो जाएगा) लेकिन कुल योग अधिकतम होगा।
या
यदि N>K तो K ऋणात्मक संख्याओं का चिह्न बदलें और सरणी जोड़ें। योग अधिकतम होगा।
इनपुट
Arr[]= { 0,-2,6,4,8,2,-3 } K=4 आउटपुट
Maximum array sum is : 25
स्पष्टीकरण − तत्वों में 4 परिवर्तन हैं
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
इनपुट
Arr[]= { -1,-2,-3,-4,-5,-6,-7 } K=4 आउटपुट
Maximum array sum is : 16
स्पष्टीकरण − तत्वों में 4 परिवर्तन हैं
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
नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है
-
पूर्णांक सरणी Arr[] का उपयोग पूर्णांकों को संग्रहीत करने के लिए किया जाता है।
-
पूर्णांक 'आकार' सरणी की लंबाई को संग्रहीत करता है और K को प्रारंभ किया जाता है।
-
फ़ंक्शन रिटर्नसम (इंट एआर [], इंट एन, इंट के) इनपुट के रूप में एक सरणी, उसका आकार और के लेता है और ठीक के संचालन के बाद इसके तत्वों का अधिकतम योग देता है।
-
सबसे पहले हम सॉर्ट (arr,arr+n)
. का उपयोग करके सरणी को सॉर्ट करेंगे -
अब हम ऑपरेशन arr[i]*-1 को सभी नकारात्मक तत्वों पर तब तक लागू करेंगे जब तक या तो अंतिम अनुक्रमणिका नहीं पहुंच जाती या k 0 नहीं हो जाता।
-
यदि k नकारात्मक तत्वों की संख्या से छोटा है, तो उपरोक्त चरण k -ve तत्वों को बदल देगा।
-
यदि k बड़ा है और k का शेष मान विषम या सम है तो जाँचा जाएगा।
-
यदि शेष k विषम है तो हम ऑपरेशन arr[i]*-1 एक बार लागू करके न्यूनतम तत्व के मान को बदल देंगे, जहां arr[i] कम से कम पाया जाता है। (-1 विषम बार से गुणा करना एक बार करने के समान है)
-
यदि शेष k सम है तो arr[i]*-1 का कोई प्रभाव नहीं पड़ेगा। कुछ मत करो।
-
संपूर्ण सरणी के योग की गणना करें और परिणाम लौटाएं।
उदाहरण
#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;
} आउटपुट
Maximum array sum that can be obtained after exactly k changes : 24