我們有兩個整數數組，一個具有計算的元素，另一個具有分割數組以產生子集所需的分割點，我們必須計算每個分割中每個子集的總和並傳回最大子集
讓我們透過範例來理解：-
#輸入− int arr[] = int arr[] = { 9, 4, 5, 6 , 7 } int splitPoints[] = { 0, 2, 3, 1 };
輸出− 每次分割後的最大子數組和[22, 13, 9 , 9]
解釋− 這裡我們根據陣列的分割點來分解數組，並在每次分割後得到最大子集和
第一次分割後 strong> → {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
第四次分割後 →{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])
- #將將 設為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] 新增] ])
建立一個類別類別subSets 並宣告first、last和value作為其資料成員，並將預設建構子定義為subSets(int f, int l, int v)，並將first設為f，last設為l，value設定為v
-
#建立一個公共方法作為比較並檢查IF s2.value 不等於到s1.value，然後返回s2.value - s1.value。 p>
範例
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
登入後複製
以上是在Java中，將陣列分割為基於給定查詢的子數組後，找到子數組的最大子數組和的詳細內容。更多資訊請關注PHP中文網其他相關文章！
