জাভাতে দেওয়া কোয়েরি অনুযায়ী অ্যারে সাবঅ্যারেতে ভাগ করে সর্বোচ্চ সাবঅ্যারে যোগফল

আমাদের দুটি পূর্ণসংখ্যা অ্যারে দেওয়া আছে, যেনের একটিে গাণনা করার উপাদানগুলো আছে এবং অন্যটিতে স্প্লিট পয়েন্ট বা বিভাজন বিন্দুগুলো আছে যেগুলো দিয়ে অ্যারেটি সাবসেট বা উপসেট বানাতে হবে এবং প্রতিটি স্প্লিটের পর প্রতিটি সাবসেটের যোগফল বের করে সর্বোচ্চ সাবসেট যোগফল ফেরত দিতে হবে।

উদাহরণ দিয়ে বুঝি

উদাহরণ ১

ইনপুট: int arr[] = { 9, 4, 5, 6, 7 }, int splitPoints[] = { 0, 2, 3, 1 };

আউটপুট: প্রতিটি স্প্লিটের পর সর্বোচ্চ সাবঅ্যারে যোগফল [22, 13, 9, 9]

ব্যাখ্যা: এখানে আমরা স্প্লিট পয়েন্ট অনুযায়ী অ্যারেটি ভাঙছি এবং প্রতিটি স্প্লিটের পর সর্বোচ্চ সাবসেট যোগফল বের করছি।

• প্রথম স্প্লিটের পর: {9} এবং {4,5,6,7} → সর্বোচ্চ সাবঅ্যারে যোগফল ২২
• দ্বিতীয় স্প্লিটের পর: {9}, {4,5} এবং {6,7} → সর্বোচ্চ সাবঅ্যারে যোগফল ১৩
• তৃতীয় স্প্লিটের পর: {9}, {4,5}, {6} এবং {7} → সর্বোচ্চ সাবঅ্যারে যোগফল ৯
• চতুর্থ স্প্লিটের পর: {9}, {4}, {5}, {6} এবং {7} → সর্বোচ্চ সাবঅ্যারে যোগফল ৯

উদাহরণ ২

ইনপুট: int arr[] = { 7, 8, 5, 9, 1 }, int splitPoints[] = { 1, 2, 0, 3 };

আউটপুট: প্রতিটি স্প্লিটের পর সর্বোচ্চ সাবঅ্যারে যোগফল [15, 115, 10, 9]

ব্যাখ্যা: স্প্লিট পয়েন্ট অনুযায়ী অ্যারে ভাগ করে সর্বোচ্চ সাবসেট যোগফল নির্ণয়।

• প্রথম স্প্লিট: {7,8} এবং {5,9,1} → সর্বোচ্চ যোগফল ১৫
• দ্বিতীয় স্প্লিট: {7,8}, {5} এবং {9,1} → সর্বোচ্চ যোগফল ১১৫
• তৃতীয় স্প্লিট: {7}, {8}, {5} এবং {9,1} → সর্বোচ্চ যোগফল ১০
• চতুর্থ স্প্লিট: {7}, {8}, {5}, {9} এবং {1} → সর্বোচ্চ যোগফল ৯

প্রোগ্রামে ব্যবহৃত পদ্ধতি

• main() মেথড থেকে শুরু করা হয়
• ইনপুট অ্যারে arr[] এবং splitPoints[] এর দৈর্ঘ্য নির্ণয় করে calculateSubsetSum(arr.length, splitPoints.length, splitPoints, arr) মেথড কল করা হয়
• calculateSubsetSum() মেথডের ভিতরে:
  • একটি sum[] অ্যারে তৈরি করা হয় এবং sum[0] = arr[0] সেট করা হয়
  • i=1 থেকে n-1 পর্যন্ত লুপ চালিয়ে sum[i] = sum[i-1] + arr[i] গণনা করা হয়
  • temp[0] = new subSets(0, n-1, sum[n-1]) সেট করা হয়
  • t2.add(temp[0]) এবং t1.add(0) যোগ করা হয়
  • splitPoints অ্যারের দৈর্ঘ্য পর্যন্ত লুপ চালানো হয়:
    • currentSplitPoint = t1.floor(splitPoints[i])
    • 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().value প্রিন্ট করা হয়
• subSets ক্লাস তৈরি করা হয় first, last, value ডেটা মেম্বারসহ এবং কনস্ট্রাক্টর subSets(int f, int l, int v)
• utilityComparator ক্লাস Comparator ইমপ্লিমেন্ট করে compare মেথড ওভাররাইড করা হয়

উদাহরণ কোড

import java.io.IOException; 
import java.io.InputStream; 
import java.util.*; 

class utilityComparator implements Comparator { 
    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 t1 = new TreeSet<>(); 
        TreeSet 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