数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究基于给定查询将数组划分为子数组后的最大子数组和（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() 的值。
创建一个名为 subSets 的类，并声明 first、last 和 value 作为其数据成员，并定义默认构造函数 subSets(int f, int l, int v)，并将 first 设置为 f，last 设置为 l，value 设置为 v。
创建一个名为 utilityComparator 的类，它将实现 Comparator<subSets>。
创建一个名为 compare 的公共方法，并检查 IF s2.value 不等于 s1.value，则返回 s2.value - s1.value。
检查 IF s1.first 不等于 s2.first，则返回 s2.first - s1.first。
Learn Java in-depth with real-world projects through our Java certification course. Enroll and become a certified expert to boost your career.
示例
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
250 次浏览
