জাভাতে প্রদত্ত প্রশ্নের উপর ভিত্তি করে অ্যারেকে সাব্যারেতে ভাগ করার পরে সর্বাধিক সাবয়ারের যোগফল

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

উদাহরণ দিয়ে বোঝা যাক:-

ইনপুট − 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) হিসাবে পদ্ধতিতে যান।

• পদ্ধতির ভিতরে সাবসেটসাম()

  গণনা করুন

  • যোগফল [] হিসাবে একটি পূর্ণসংখ্যা অ্যারে তৈরি করুন এবং যোগফল[0] কে arr[0] হিসাবে সেট করুন।

  • একটি অ্যারের দৈর্ঘ্য পর্যন্ত i থেকে 1 পর্যন্ত লুপ শুরু করুন এবং যোগফল[i] কে যোগফল [i - 1] + arr[i] সেট করুন এবং temp[0] কে নতুন উপসেটগুলিতে সেট করুন(0, n - 1, যোগফল[n - 1])।

  • t2.add(temp[0]) এবং t1.add(0)

    যোগ করতে থাকুন

  • স্প্লিটপয়েন্ট অ্যারের দৈর্ঘ্য পর্যন্ত i থেকে 0 পর্যন্ত লুপ শুরু করুন। লুপের ভিতরে currentSplitPoint কে t1.floor(splitPoints[i]) এ সেট করুন এবং t2 থেকে t2.remove(temp[currentSplitPoint])

  • temp[currentSplitPoint].stast এবং temp[currentSplitPoint] নতুন সাবসেট হিসেবে সেট করুন(currentSplitPoint, splitPoints[i], sum[splitPoints[i]] - (currentSplitPoint ==0 ? 0 :যোগফল[currentSplitPoint - 1])) /P>

  • t2.add(temp[currentSplitPoint]) এবং temp[splitPoints[i] + 1] =নতুন উপসেট(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() মান।

• ক্লাস সাবসেট হিসাবে একটি ক্লাস তৈরি করুন এবং এর ডেটা সদস্য হিসাবে প্রথম, শেষ এবং মান ঘোষণা করুন এবং ডিফল্ট কনস্ট্রাক্টরকে সাবসেট হিসাবে সংজ্ঞায়িত করুন (int f, int l, int v) এবং প্রথমে f, শেষ থেকে l এবং মান v এ সেট করুন

• ইউটিলিটি কম্পারেটর হিসাবে একটি ক্লাস তৈরি করুন যা তুলনাকারী<সাবসেট>

  কে কার্যকর করবে

  • তুলনা হিসাবে একটি সর্বজনীন পদ্ধতি তৈরি করুন এবং চেক করুন যদি 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