In Java, find the maximum subarray sum of subarrays after splitting an array into subarrays based on a given query

We have two arrays of integers, one with calculated elements and the other with the split points required to split the array to generate subsets, we have to calculate each subset in each split The sum of and returns the maximum subset

Let us understand through an example:-

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

Output− The maximum subarray sum after each split [22, 13, 9 , 9]

Explanation− Here we decompose the array according to its split points, and obtain the maximum subset sum after each split

First After the second split strong> → {9} and {4,5,6,7} >> The maximum subarray sum is - 22

After the second split → {9} , {4,5} and {6,7} >> The maximum subarray sum is - 13

After the third split →{9}, {4,5}, { 6} and {7} >> The maximum subarray sum is - 9

After the fourth split →{9}, {4}, {5}, {6} and { 7} >> Maximum subarray sum is- 9

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

Output−The maximum subarray sum after each division [15, 115, 10, 9]

Explanation−Here we decompose the array according to its split points, and obtain the maximum subset sum after each split

After the first split → {7, 8} and {5,9,1} >> The maximum subarray sum is 15

After the second split → {7,8}, {5} and {9,1 } >> The maximum sub-array sum is 115

After the third split →{7}, {8}, {5} and {9,1} >> The maximum sub-array sum is 10

After the fourth split →{7}, {8}, {5}, {9} and {1} >> the maximum sub-array sum is 9

The methods used in the following program are as follows -

• We will start from the main() method

  • Enter the array of any given length , such as arr[] and splitPoints[]. Their lengths are calculated and passed to the method in the form calculateSubsetSum(arr.length, splitPoints.length, splitPoints, arr).

• In the method calculateSubsetSum()

  • Create an integer array as sum[] and set sum[0 ] is set to arr[0].

  • Start looping FOR from i to 1 until the length of the array, and set sum[i] to sum[i - 1] arr[i] and set temp[0] to new subSets(0, n - 1, sum[n - 1]).

  • Continue to add t2.add(temp[0]) and t1.add(0)

  • Start looping FOR from i to 0, up to the length of the splitPoints array. Inside the loop set currentSplitPoint to t1.floor(splitPoints[i]) and remove from t2 to t2.remove(temp[currentSplitPoint])

  • Set end to temp[currentSplitPoint ] .last and temp[currentSplitPoint] as new subSets(currentSplitPoint, splitPoints[i], sum[splitPoints[i]] - (currentSplitPoint == 0 ? 0 : sum[currentSplitPoint - 1]))

  • Use t2.add(temp[currentSplitPoint]) and 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) and t1.add(splitPoints[i] to add 1)

  • Print t2.first() value.

• Create a class subSets and declare first, last and value as its data members and define the default constructor as subSets(int f, int l, int v), and set first to f, last to l, and value to v

• Create a class as utilityComparator, which will implement Comparator
  • Create a public method as a comparison and check IF s2.value is not equal to s1.value, then return s2.value - s1.value.

  • Check whether s1.first is not equal to s2.first, and then return s2.first - s1.first

    p>

Example

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

If we run the above code it will generate the following output

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

The above is the detailed content of In Java, find the maximum subarray sum of subarrays after splitting an array into subarrays based on a given query. For more information, please follow other related articles on the PHP Chinese website!