資料結構
網路
關係型資料庫管理系統
作業系統
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。
示例
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 次瀏覽
