En Java, recherchez la somme maximale des sous-tableaux après avoir divisé un tableau en sous-tableaux en fonction d'une requête donnée.

Nous avons deux tableaux d'entiers, l'un avec les éléments calculés et l'autre avec les points de division nécessaires pour diviser le tableau afin de générer des sous-ensembles, nous devons calculer la somme de chaque sous-ensemble dans chaque division et renvoyer le sous-ensemble maximum

Comprenons par exemple :-

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

Sortie− La somme maximale du sous-tableau [22, 13, 9, 9] après chaque division Somme du sous-ensemble

Après la première division → {9} et {4,5,6,7} >> La somme maximale du sous-tableau est de - 22

Après la deuxième division strong> → {9}, { 4,5 } et {6,7} >> La somme maximale du sous-tableau est de - 13

Après la troisième division →{ 9}, {4,5}, {6} et {7} >> Le sous-tableau maximum La somme du tableau est - 9

Après la quatrième division →{9}, {4}, {5}, {6 } et {7} >> La somme maximale du sous-tableau est- 9

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

Sortie−La somme maximale du sous-tableau après chaque division [15, 115, 10, 9]

Explication−Ici, nous décomposons le tableau en fonction de ses points de division et obtenons la somme maximale du sous-ensemble après chaque division

Après la première division → {7, 8} et {5,9,1} >> La somme maximale du sous-tableau est de 15

Après la deuxième division → {7,8}, {5} et {9,1} >> La somme maximale des sous-tableaux est de 15 115

Après la troisième division →{7}, {8}, {5} et {9,1} >> Le maximum la somme du sous-tableau est de 10

Après la quatrième division →{7}, {8}, {5}, {9} et {1} >> La somme maximale du sous-tableau est de 9

La méthode utilisée dans le Le programme suivant est le suivant : 

Nous commencerons par la méthode main()

• Tableaux d'entrée de n'importe quelle longueur donnée, tels que arr[] et splitPoints[]. Leurs longueurs sont calculées et transmises à la méthode sous la forme calculateSubsetSum(arr.length, splitPoints.length, splitPoints, arr).

  Dans la méthode calculateSubsetSum()

• créez un tableau d'entiers sous la forme sum[] et définissez sum[0] sur arr[0].

  • Démarrez la boucle FOR de i à 1 jusqu'à la longueur du tableau, et définissez sum[i] sur sum[i - 1] + arr[i] et définissez temp[0] sur new subSets(0, n - 1, somme[n - 1]).

  • Continuez à ajouter t2.add(temp[0]) et t1.add(0)

  • Démarrez la boucle FOR de i à 0 jusqu'à la longueur du tableau splitPoints. À l'intérieur de la boucle, définissez currentSplitPoint sur t1.floor(splitPoints[i]) et supprimez de t2 à t2.remove(temp[currentSplitPoint])

  • set end sur temp[currentSplitPoint] .last et temp[currentSplitPoint] en tant que nouveaux sous-ensembles (currentSplitPoint, splitPoints[i], sum[splitPoints[i]] - (currentSplitPoint == 0 ? 0 : sum[currentSplitPoint - 1]))

  • utilisez t2.add(temp[currentSplitPoint]) et temp[splitPoints [i] + 1] = nouveaux sous-ensembles (splitPoints[i] + 1, fin, somme[end] - somme[splitPoints[i] add]])

  • utilisez t2.add(temp[splitPoints [i] + 1]), t1.add(currentSplitPoint) et t1.add(splitPoints[i] + to add 1)

  • Imprimez la valeur t2.first().

  Créez des sous-ensembles de classe et déclarez le premier, le dernier et la valeur comme membres de données et définissez le constructeur par défaut en tant que sous-ensembles (int f, int l, int v) et définissez le premier sur f, le dernier Set sur l et la valeur to v

• Créez une classe en tant qu'utilitaireComparator qui implémentera Comparator

• Créez une méthode publique comme comparaison et vérifiez si s2.value n'est pas égal à s1.value, puis renvoyez la valeur s2 - s1.value.

  • Vérifiez si s1.first n'est pas égal à s2.first et renvoyez s2.first - s1.first

  • p>

  Exemple

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

Output

Si nous exécutons le code ci-dessus, il générera la sortie suivante

Maximum subarray sum after each split
49
49
49
49
44
34

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!