हमें दो पूर्णांक सरणी दी गई हैं, एक में वे तत्व हैं जिनकी गणना की जानी है और दूसरे में वे विभाजन बिंदु हैं जिनकी आवश्यकता सरणी को उपसमुच्चय बनाने के लिए विभाजित करने के लिए होती है और हमें प्रत्येक विभाजन में प्रत्येक उपसमुच्चय का योग निकालना है और अधिकतम उपसमुच्चय योग वापस करना है।
आइए उदाहरण से समझते हैं:-
इनपुट - int arr[] = int arr[] = { 9, 4, 5, 6, 7 } int splitPoints[] = { 0, 2, 3, 1 };
आउटपुट - प्रत्येक विभाजन के बाद अधिकतम उपसरणी योग [22, 13, 9, 9]
व्याख्या - यहां हम उनके विभाजन बिंदुओं के अनुसार सरणी को तोड़ रहे हैं और प्रत्येक विभाजन के बाद अधिकतम उपसमुच्चय योग प्राप्त कर रहे हैं
पहले विभाजन के बाद → {9} और {4,5,6,7} >> अधिकतम उपसरणी योग है - 22
दूसरे विभाजन के बाद → {9}, {4,5} और {6,7} >> अधिकतम उपसरणी योग है - 13
तीसरे विभाजन के बाद → {9}, {4,5}, {6} और {7} >> अधिकतम उपसरणी योग है - 9
चौथे विभाजन के बाद → {9}, {4}, {5}, {6} और {7} >> अधिकतम उपसरणी योग है - 9
इनपुट - int arr[] = int arr[] = { 7, 8, 5, 9, 1 } int splitPoints[] = { 1, 2, 0, 3 };
आउटपुट - प्रत्येक विभाजन के बाद अधिकतम उपसरणी योग [15, 115, 10, 9]
व्याख्या - यहां हम उनके विभाजन बिंदुओं के अनुसार सरणी को तोड़ रहे हैं और प्रत्येक विभाजन के बाद अधिकतम उपसमुच्चय योग प्राप्त कर रहे हैं
पहले विभाजन के बाद → {7,8} और {5,9,1} >> अधिकतम उपसरणी योग है 15
दूसरे विभाजन के बाद → {7,8}, {5} और {9,1} >> अधिकतम उपसरणी योग है 115
तीसरे विभाजन के बाद → {7}, {8}, {5} और {9,1} >> अधिकतम उपसरणी योग है 10
चौथे विभाजन के बाद → {7}, {8}, {5}, {9} और {1} >> अधिकतम उपसरणी योग है 9
नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण इस प्रकार है -
हम main() विधि से शुरू करेंगे
किसी भी दी गई लंबाई के इनपुट सरणी मान लें, arr[] और splitPoints[]। उनकी लंबाई की गणना करें और विधि को calculateSubsetSum(arr.length, splitPoints.length, splitPoints, arr) के रूप में पास करें।
विधि calculateSubsetSum() के अंदर
एक पूर्णांक सरणी बनाएं जैसे sum[] और sum[0] को arr[0] के रूप में सेट करें।
i से 1 तक सरणी की लंबाई तक FOR लूप शुरू करें और sum[i] को sum[i - 1] + arr[i] के रूप में सेट करें और temp[0] को new subSets(0, n - 1, sum[n - 1]) के रूप में सेट करें।
t2.add(temp[0]) और t1.add(0) जोड़ते रहें
i से 0 तक splitPoints सरणी की लंबाई तक FOR लूप शुरू करें। लूप के अंदर currentSplitPoint को t1.floor(splitPoints[i]) के रूप में सेट करें और t2 से hटाएं जैसे t2.remove(temp[currentSplitPoint])
end को temp[currentSplitPoint].last के रूप में सेट करें और temp[currentSplitPoint] को new subSets(currentSplitPoint, splitPoints[i], sum[splitPoints[i]] - (currentSplitPoint == 0 ? 0 : sum[currentSplitPoint - 1])) के रूप में सेट करें
t2.add(temp[currentSplitPoint]) का उपयोग करके जोड़ें और temp[splitPoints[i] + 1] = new subSets(splitPoints[i] + 1, end, sum[end] - sum[splitPoints[i]])
t2.add(temp[splitPoints[i] + 1]), t1.add(currentSplitPoint) और t1.add(splitPoints[i] + 1) का उपयोग करके जोड़ें
t2.first() मान प्रिंट करें।
subSets नामक एक वर्ग बनाएं और इसके डेटा सदस्यों के रूप में first, last और value घोषित करें और डिफ़ॉल्ट कंस्ट्रक्टर को subSets(int f, int l, int v) के रूप में परिभाषित करें और first को f, last को l और value को v पर सेट करें
utilityComparator नामक एक वर्ग बनाएं जो Comparator
को IMPLEMENTS करेगा compare नामक एक सार्वजनिक विधि बनाएं और जांचें IF s2.value s1.value के बराबर नहीं है तो s2.value - s1.value वापस करें।
जांचें IF s1.first s2.first के बराबर नहीं है तो s2.first - s1.first वापस करें
उदाहरण
import java.io.IOException; import java.io.InputStream; import java.util.*; class utilityComparator implements Comparator<subSets>{ public int compare(subSets s1, subSets s2){ if(s2.value != s1.value){ return s2.value - s1.value; } if(s1.first != s2.first){ return s2.first - s1.first; } return 0; } } class subSets{ int first; int last; int value; subSets(int f, int l, int v){ first = f; last = l; value = v; } } public class testClass{ static void calculateSubsetSum(int n, int k, int splitPoints[], int arr[]){ int sum[] = new int[n]; sum[0] = arr[0]; for (int i = 1; i < n; i++){ sum[i] = sum[i - 1] + arr[i]; } TreeSet<Integer> t1 = new TreeSet<>(); TreeSet<subSets> t2 = new TreeSet<>(new utilityComparator()); subSets temp[] = new subSets[n]; temp[0] = new subSets(0, n - 1, sum[n - 1]); t2.add(temp[0]); t1.add(0); System.out.println("Maximum subarray sum after each split"); for (int i = 0; i < k; i++){ int currentSplitPoint = t1.floor(splitPoints[i]); t2.remove(temp[currentSplitPoint]); int end = temp[currentSplitPoint].last; temp[currentSplitPoint] = new subSets(currentSplitPoint, splitPoints[i], sum[splitPoints[i]] - (currentSplitPoint == 0 ? 0 : sum[currentSplitPoint - 1])); t2.add(temp[currentSplitPoint]); temp[splitPoints[i] + 1] = new subSets(splitPoints[i] + 1, end, sum[end] - sum[splitPoints[i]]); t2.add(temp[splitPoints[i] + 1]); t1.add(currentSplitPoint); t1.add(splitPoints[i] + 1); System.out.println(t2.first().value); } } public static void main(String[] args){ int arr[] = { 2, 1, 6, 8, 5, 10, 21, 13}; int splitPoints[] = { 3, 1, 2, 0, 4, 5 }; calculateSubsetSum(arr.length, splitPoints.length, splitPoints, arr); } }आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो यह निम्नलिखित आउटपुट उत्पन्न करेगा
Maximum subarray sum after each split 49 49 49 49 44 34
