在Java中，将数组分割为基于给定查询的子数组后，找到子数组的最大子数组和

我们有两个整数数组，一个具有计算的元素，另一个具有分割数组以生成子集所需的分割点，我们必须计算每个分割中每个子集的总和并返回最大子集

让我们通过示例来理解：-

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

输出− 每次分割后的最大子数组和 [22, 13, 9, 9]< /p>

解释− 这里我们根据数组的分割点来分解数组，并在每次分割后获得最大子集和

第一次分割后 → {9} 和 {4,5,6,7} >> 最大子数组总和为 - 22

第二次分割后 → {9}, {4,5 } 和 {6,7} >> 最大子数组和为 - 13

第三次分割后 →{9}、{4,5}、{6} 和 {7} >> 最大子数组和为 - 9

第四次分割后 →{9}、{4}、{5}、{6} 和 {7} >> 最大子数组和is- 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

< strong>第四次分割后 →{7}、{8}、{5}、{9} 和 {1} >> 最大子数组和为 9

以下程序中使用的方法是如下 -

• 我们将从 main() 方法开始

  • 输入数组任何给定长度，例如 arr[] 和 splitPoints[]。计算它们的长度并以calculateSubsetSum(arr.length, splitPoints.length, splitPoints, arr)的形式传递给方法。

• 在方法calculateSubsetSum中()

  • 创建一个整数数组作为 sum[]，并将 sum[0] 设置为 arr[0]。

  • 开始循环 FOR 从 i 到 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)

  • 从 i 到 0 开始循环 FOR，直到 splitPoints 数组的长度。在循环内部将 currentSplitPoint 设置为 t1.floor(splitPoints[i]) 并从 t2 中删除为 t2.remove(temp[currentSplitPoint])

  • 将 end 设置为 temp[currentSplitPoint] .last 和 temp[currentSplitPoint] 作为新的 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() 值。

• 创建一个类类 subSets 并声明first、last和value作为其数据成员，并将默认构造函数定义为subSets(int f, int l, int v)，并将first设置为f，last设置为l，value设置为v

• 创建一个类作为 utilityComparator，它将实现 Comparator

  • 创建一个公共方法作为比较并检查 IF s2.value 不等于到 s1.value，然后返回 s2.value - s1.value。

  • 检查 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