Ermitteln Sie in Java die maximale Subarray-Summe von Subarrays, nachdem Sie ein Array basierend auf einer bestimmten Abfrage in Subarrays aufgeteilt haben

Wir haben zwei Arrays von Ganzzahlen, eines mit den berechneten Elementen und das andere mit den Teilungspunkten, die zum Teilen des Arrays zur Generierung von Teilmengen erforderlich sind. Wir müssen die Summe jeder Teilmenge in jeder Teilung berechnen und die maximale Teilmenge zurückgeben

Lassen Sie es uns anhand eines Beispiels verstehen:-

Input− int arr[] = int arr[] = { 9, 4, 5, 6 , 7 } int splitPoints[] = { 0, 2, 3, 1 } ;

Ausgabe− Die maximale Sub-Array-Summe [22, 13, 9, 9] nach jeder Teilung Teilmengensumme

Nach der ersten Teilung → {9} und {4,5,6,7} >> Die maximale Subarray-Summe beträgt - 22

Nach der zweiten Teilung strong> → {9}, { 4,5 } und {6,7} >> Die maximale Subarray-Summe beträgt - 13

Nach der dritten Teilung →{ 9}, {4,5}, {6} und {7} >> Das maximale Subarray. Die Array-Summe beträgt - 9

Nach der vierten Teilung →{9}, {4}, {5}, {6 } und {7} >> Die maximale Subarray-Summe beträgt 9

Input−int arr[] = int arr[] = { 7, 8, 5, 9, 1 } int splitPoints[] = { 1, 2 , 0, 3 };

Ausgabe−Die maximale Subarray-Summe nach jeder Teilung [15, 115, 10, 9]

Erklärung−Hier zerlegen wir das Array entsprechend seinen Teilungspunkten und erhalten die maximale Teilmengensumme nach jeder Aufteilung

Nach der ersten Aufteilung → {7, 8} und {5,9,1} >> Die maximale Sub-Array-Summe beträgt 15

Nach der zweiten Aufteilung → {7,8}, {5} und {9,1} >> Die maximale Sub-Array-Summe beträgt 115

Nach der dritten Division →{7}, {8}, {5} und {9,1} >> Die maximale Sub-Array-Summe beträgt 115 -Array-Summe ist 10

Nach der vierten Division →{7}, {8}, {5}, {9} und {1} >> Die maximale Sub-Array-Summe beträgt 9

Die im Folgenden verwendete Methode Das Programm lautet wie folgt:

Wir beginnen mit der Methode main()

• Geben Sie Arrays beliebiger Länge ein, z. B. arr[] und splitPoints[]. Ihre Längen werden berechnet und in der Form berechneSubsetSum(arr.length, splitPoints.length, splitPoints, arr) an die Methode übergeben.

  Erstellen Sie in der Methode berechneSubsetSum()

• ein ganzzahliges Array als sum[] und setzen Sie sum[0] auf arr[0].

  • Beginne eine FOR-Schleife von i nach 1 bis zur Länge des Arrays und setze sum[i] auf sum[i - 1] + arr[i] und setze temp[0] auf neue Teilmengen(0, n - 1, sum[n - 1]).

  • Fahren Sie mit dem Hinzufügen von t2.add(temp[0]) und t1.add(0) fort

  • Beginnen Sie mit der FOR-Schleife von i bis 0, bis die Länge des splitPoints-Arrays erreicht ist. Innerhalb der Schleife setze currentSplitPoint auf t1.floor(splitPoints[i]) und entferne von t2 auf t2.remove(temp[currentSplitPoint])

  • setze end auf temp[currentSplitPoint] .last und temp[currentSplitPoint] als neue Teilmengen (currentSplitPoint, splitPoints[i], sum[splitPoints[i]] - (currentSplitPoint == 0 ? 0 : sum[currentSplitPoint - 1]))

  • Verwenden Sie t2.add(temp[currentSplitPoint]) und temp[splitPoints [i] + 1] = new subSets(splitPoints[i] + 1, end, sum[end] - sum[splitPoints[i] add]])

  • use t2.add(temp[splitPoints [i] + 1]), t1.add(currentSplitPoint) und t1.add(splitPoints[i] + zum Addieren von 1)

  • Drucken Sie den t2.first()-Wert aus.

  Erstellen Sie eine Klasse subSets und deklarieren Sie first, last und value als ihre Datenelemente und definieren Sie den Standardkonstruktor als subSets(int f, int l, int v) und setzen Sie first auf f, last Set auf l und value zu v

• Erstellen Sie eine Klasse als UtilityComparator, die Comparator implementiert

• Erstellen Sie eine öffentliche Methode als Vergleich und prüfen Sie, ob s2.value nicht gleich s1.value ist, und geben Sie dann s2 value - s1.value zurück.

  • Überprüfen Sie, ob s1.first nicht gleich s2.first ist, und geben Sie s2.first - s1.first zurück

    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);
       }
    }

Das obige ist der detaillierte Inhalt vonErmitteln Sie in Java die maximale Subarray-Summe von Subarrays, nachdem Sie ein Array basierend auf einer bestimmten Abfrage in Subarrays aufgeteilt haben. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!