根据Java中给定的查询将数组划分为子数组后的最大子数组和
我们有两个整数数组，一个具有计算的元素，另一个具有拆分数组以制作子集所需的拆分点，我们必须计算每个拆分中每个子集的总和并返回最大子集总和。
让我们用例子来理解：-
输入 -intarr[]=intarr[]={9,4,5,6,7}intsplitPoints[]={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
输入 -intarr[]=intarr[]={7,8,5,9,1}intsplitPoints[]={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)传递给方法。
方法里面calculateSubsetSum()
创建一个整数数组作为sum[]并将sum[0]设置为arr[0]。
从i到1开始循环FOR直到数组的长度并将sum[i]设置为sum[i-1]+arr[i]并将temp[0]设置为newsubSets(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])
将结束设置为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]=newsubSets(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()
创建一个类作为类子集并将first、last和value声明为其数据成员，并将默认构造函数定义为subSets(intf,intl,intv)并将first设置为f，last设置为l并将值设置为v
创建一个类作为utilityComparator，它将实现Comparator<subSets>
创建一个公共方法作为比较并检查IFs2.value不等于s1.value然后返回s2.value-s1.value。
检查IFs1.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){
returns2.value- s1.value;
}
if(s1.first != s2.first){
returns2.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