Java では、指定されたクエリに基づいて配列を部分配列に分割した後、部分配列の最大部分配列合計を見つけます。

2 つの整数配列があり、1 つは計算された要素を持ち、もう 1 つは配列を分割してサブセットを生成するために必要な分割ポイントを持ちます。各分割で各サブセットを計算する必要があります。

例を通して理解してみましょう:-

Input- int arr[] = int arr[] = { 9, 4, 5 , 6, 7 } int splitPoints[] = { 0, 2, 3, 1 };

Output- 各分割後の最大サブ配列合計 [22, 13, 9 , 9]

説明- ここでは、分割点に従って配列を分解し、各分割後の最大サブセット合計を取得します。

最初 2 番目の分割後 strong> → {9} と {4,5,6,7} >> 部分配列の最大合計は - 22

2 番目の分割後 → {9} , {4,5} and {6,7} >> サブ配列の最大合計は - 13

3 回目の分割後 →{9}、{4,5}、{ 6}、および {7} > > サブ配列の最大合計は - 9

4 番目の分割後 →{9}、{4}、{5}、{6}、および { 7} >> サブ配列の最大合計は次のとおりです- 9

input−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

2 番目の分割後 → {7,8}、{5}、および {9,1 } >> サブ配列の合計の最大値は 115

3 回目の分割後 →{7}、{8}、{5}、および {9,1} >> サブ配列の最大合計は 10

After 4 番目の分割 →{7}、{8}、{5}、{9}、および {1} >> 部分配列の最大合計は 9

次のプログラムで使用されるメソッドは次のとおりです。以下のように -

• main() メソッドから開始します

  • arr[] や arr[] などの任意の長さの配列を入力します。スプリットポイント[]。それらの長さは計算され、calculateSubsetSum(arr.length, SplitPoints.length, SplitPoints, arr) の形式でメソッドに渡されます。

• メソッド CalculateSubsetSum()

  • 整数配列を sum[] として作成し、 sum[0 ] を設定します。 arr[0]に設定されます。

  • i から 1 まで配列の長さになるまで FOR のループを開始し、sum[i] を sum[i - 1] arr[i] に設定し、temp[0] を に設定します。新しいサブセット(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]) に削除します

  • end を temp[currentSplitPoint ] .last に設定します。および temp[currentSplitPoint] を新しいサブセットとして (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] add] ])を使用します

  • t2.add(temp[splitPoints[i] 1])、t1.add(currentSplitPoint)、および t1.add(splitPoints[i] to add 1)

  • t2.first() 値を出力します。

• クラスの subSet を作成し、first、last、value をそのデータ メンバーとして宣言し、デフォルトのコンストラクターを subSets(int f, int l, int v) として定義します。を設定し、first を f、last を l、value を v

• Comparator を実装するクラスをutilityComparatorとして作成します
  #比較としてパブリック メソッドを作成し、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 中国語 Web サイトの他の関連記事を参照してください。