Javaで指定されたクエリに基づいて、配列をサブ配列に分割した後の最大サブ配列の合計

2つの整数配列が与えられます。1つは計算される要素を持ち、もう1つはサブセットを作成するために配列を分割するために必要な分割点を持ち、すべての分割で各サブセットの合計を計算し、最大サブセット合計を返す必要があります。

例を挙げて理解しましょう：-

入力 − 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

2回目の分割後 →{9}、{4,5}、{6,7}>>サブアレイの最大合計は-13

3回目の分割後 →{9}、{4,5}、{6}、{7}>>サブアレイの最大合計は-9

4回目の分割後 →{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です

2回目の分割後 →{7,8}、{5}、{9,1}>>サブアレイの最大合計は115

3回目の分割後 →{7}、{8}、{5}、{9,1}>>サブアレイの最大合計は10です

4回目の分割後 →{7}、{8}、{5}、{9}、および{1}>>サブアレイの最大合計は9です

以下のプログラムで使用されるアプローチは次のとおりです-

• main（）メソッドから始めます

  • 任意の長さの入力配列、たとえばarr[]とsplitPoints[]。それらの長さを計算し、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]を新しいsubSets（0、n-1、sum [n- 1]）。

  • t2.add（temp [0]）とt1.add（0）を追加し続けます

  • splitPoints配列の長さまでiから0までループFORを開始します。ループ内で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]]）>

  • 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に設定します

• Comparator

  を実装するutilityComparatorとしてクラスを作成します

  • 比較としてパブリックメソッドを作成し、s2.valueがs1.valueと等しくないかどうかを確認してからs2.value-s1.valueを返します。

  • 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