在Java中，將陣列分割為基於給定查詢的子數組後，找到子數組的最大子數組和

我們有兩個整數數組，一個具有計算的元素，另一個具有分割數組以產生子集所需的分割點，我們必須計算每個分割中每個子集的總和並傳回最大子集

讓我們透過範例來理解：-

#輸入− 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] 新增] ])
  使用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

• #建立一個公共方法作為比較並檢查IF s2.value 不等於到s1.value，然後返回s2.value - s1.value。
  檢查s1.first 是否不等於s2.first，然後回傳s2.first - s1.first

  • 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中文網其他相關文章！