हमें धनात्मक और ऋणात्मक पूर्णांकों की एक सरणी और एक संख्या K दी गई है। कार्य सरणी के तत्वों में ठीक K परिवर्तन करने के बाद सरणी का अधिकतम योग ज्ञात करना है। एकल परिवर्तन संक्रिया यहां किसी एक तत्व को -1 से गुणा करना है।
उपयोग किया गया दृष्टिकोण हर ऋणात्मक संख्या को धनात्मक में बदलना है। यदि N ऋणात्मक संख्याएं हैं, तो इसके लिए हम सरणी को क्रमबद्ध करेंगे -
यदि N < K, तो N संक्रियाओं के बाद हर तत्व धनात्मक हो जाएगा, और हमारे पास K-N संक्रियाएं शेष रहेंगी।
अब यदि K-N सम है, तो शेष K-N संक्रियाओं के लिए चिह्न बदलने का कोई प्रभाव नहीं पड़ेगा, कुछ न करें।
यदि K-N विषम है, तो शेष K-N संक्रियाओं के लिए सबसे छोटी संख्या (जो ऋणात्मक हो जाएगी) का चिह्न बदलें लेकिन समग्र योग अधिकतम होगा।
या
यदि N > K तो K ऋणात्मक संख्याओं का चिह्न बदलें और सरणी जोड़ें। योग अधिकतम होगा।
इनपुट
Arr[]= { 0,-2,6,4,8,2,-3 } K=4
आउटपुट
अधिकतम सरणी योग है : 25
व्याख्या - तत्वों में 4 परिवर्तन हैं
1. 0,2,6,4,8,2,-3 -2 को 2 में बदला 2. 0,2,6,4,8,2,3 -3 को 3 में बदला 3. 0,-2,6,4,8,2,3 2 को -2 में बदला 4. 0,2,6,4,8,2,3 -2 को 2 में बदला अधिकतम योग 25 है
इनपुट
Arr[]= { -1,-2,-3,-4,-5,-6,-7 } K=4
आउटपुट
अधिकतम सरणी योग है : 16
व्याख्या - तत्वों में 4 परिवर्तन हैं
1. -1,-2,-3,-4,-5,-6,7 -7 को 7 में बदला 2. -1,-2,-3,-4,-5,6,7 -6 को 6 में बदला 3. -1,-2,-3,-4,5,6,7 -5 को 5 में बदला 4. -1,-2,-3,4,5,6,7 -4 को 4 में बदला अधिकतम योग 16 है
नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण इस प्रकार है
पूर्णांक सरणी Arr[] का उपयोग पूर्णांकों को संग्रहीत करने के लिए किया जाता है।
पूर्णांक 'size' सरणी की लंबाई संग्रहीत करता है और K प्रारंभिकृत होता है।
फ़ंक्शन returnSum(int arr[], int n, int k) एक सरणी, उसका आकार और k इनपुट के रूप में लेता है और ठीक k संक्रियाओं के बाद उसके तत्वों का अधिकतम योग लौटाता है।
सबसे पहले हम sort(arr, arr+n) का उपयोग करके सरणी को क्रमबद्ध करेंगे।
अब हम सभी ऋणात्मक तत्वों पर संक्रिया arr[i]*-1 लागू करेंगे जब तक कि अंतिम सूचकांक तक न पहुंच जाएं या k शून्य न हो जाए।
यदि k ऋणात्मक तत्वों की संख्या से छोटा है, तो उपरोक्त चरण k ऋणात्मक तत्वों को बदल देगा।
यदि 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(arr, arr + n); // सबसे छोटे से शुरू करके ऋणात्मक तत्वों के चिह्न बदलें // यह लूप प्रत्येक k के लिए एक ऋणात्मक तत्व को धनात्मक में बदल देगा for(i=0;i<n;i++) if(k>0 && arr[i]<0){ arr[i]=arr[i]*-1; k--; } // यदि k शून्येतर और विषम है तो न्यूनतम तत्व का चिह्न एक बार बदलें // क्योंकि यह इसके चिह्न को विषम बार बदलने के समान है if (k % 2 == 1) { int min = arr[0]; int pos=0; // न्यूनतम तत्व का सूचकांक 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 <<"ठीक k परिवर्तनों के बाद प्राप्त होने वाला अधिकतम सरणी योग" returnSum(Arr, size, K) << endl; return 0; }
आउटपुट
ठीक k परिवर्तनों के बाद प्राप्त होने वाला अधिकतम सरणी योग : 24