根据 Java 中给定的查询将数组划分为子数组后，求出最大子数组和
我们给出了两个整数数组，一个数组包含计算出的元素，另一个数组包含分割点，分割点是分割数组以生成子集所必需的，我们必须计算每次分割中每个子集的总和并返回最大子集总和。
让我们通过例子来理解:-
输入 − int arr[] = int arr[] = { 9, 4, 5, 6, 7 } int splitPoints[] = { 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
输入 −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
第四次拆分后 →{7}, {8}, {5}, {9} 和 {1} >>子数组的最大和为 9
以下程序中使用的方法如下 −
我们将从 main() 方法开始
输入任意给定长度的数组，比如说 arr[] 和 splitPoints[]。计算它们的长度并将其传递给方法，作为 calculateSubsetSum(arr.length, splitPoints.length, splitPoints, arr)。
在方法 calculateSubsetSum() 内部
创建一个整数数组作为 sum[]，并将 sum[0] 设置为 arr[0]。
从 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 开始循环，直到 splitPoints 数组的长度。在循环中将 currentSplitPoint 设置为 t1.floor(splitPoints[i])，并从 t2 中删除，即 t2.remove(temp[currentSplitPoint])
将 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)
打印 t2.first() 值。
创建一个类作为类子集，并将 first、last 和 value 声明为其数据成员，并将默认构造函数定义为子集 (int f、int l、int v)，并将 first 设置为 f、last 设置为 l、value 设置为 v
创建一个类作为 utilityComparator，它将实现 Comparator<subSets>
创建一个公共方法作为比较并检查如果 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
