C++プログラムでバイナリインデックスツリーを使用した最大合計増加部分列

この問題では、n個の整数の配列arr[]が与えられます。私たちのタスクは、C++のバイナリインデックスツリーを使用して最大合計増加部分列を見つけるプログラムを作成することです。

問題の説明 −配列の要素を使用して、合計が最大になる増加部分列を見つける必要があります。

サブシーケンスの増加 −現在の要素の値が前の位置の要素よりも大きいサブシーケンス。

バイナリインデックスツリー −ツリーの一種であるデータ構造です。効果的な方法でツリーに要素を追加したり、ツリーから要素を削除したりできます。

問題を理解するために例を見てみましょう

入力

arr[] = {5, 1, 7, 3, 8, 2}

出力

20

説明

Subsequences:
{5, 7, 8} = 5 + 7 + 8 = 20
{1, 3, 8} = 1 + 3 + 8 = 12
{1, 7, 8} = 1 + 7 + 8 = 16

ソリューションアプローチ

この問題では、binaryindexツリーを使用して可能なmaxSumを見つける必要があります。このために、配列の要素からのマップを使用してバイナリインデックスツリーを作成します。次に、配列の要素を繰り返し使用して、要素ごとに、BITの値までのすべての要素の合計を見つける必要があります。そして、すべての値の最大合計を返します。

例

ソリューションの動作を説明するプログラム

#include <bits/stdc++.h>
using namespace std;
int calcMaxSum(int BITree[], int index){
   int sum = 0;
   while (index > 0) {
      sum = max(sum, BITree[index]);
      index −= index & (−index);
   }
   return sum;
}
void updateTreeVal(int BITree[], int newIndex, int index, int sumVal){
   while (index <= newIndex) {
      BITree[index] = max(sumVal, BITree[index]);
      index += index & (−index);
   }
}
int calcMaxSumBIT(int arr[], int n){
   int uniqCount = 0, maxSum;
   map<int, int> BinaryIndexTree;
   for (int i = 0; i < n; i++) {
      BinaryIndexTree[arr[i]] = 0;
   }
   for (map<int, int>::iterator it = BinaryIndexTree.begin();
   it != BinaryIndexTree.end(); it++) {
      uniqCount++;
      BinaryIndexTree[it−>first] = uniqCount;
   }
   int* BITree = new int[uniqCount + 1];
   for (int i = 0; i <= uniqCount; i++) {
      BITree[i] = 0;
   }
   for (int i = 0; i < n; i++) {
      maxSum = calcMaxSum(BITree, BinaryIndexTree[arr[i]] − 1);
      updateTreeVal(BITree, uniqCount, BinaryIndexTree[arr[i]],
      maxSum + arr[i]);
   }
   return calcMaxSum(BITree, uniqCount);
}
int main(){
   int arr[] = {5, 1, 7, 3, 8, 2};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"The maximum sum increasing subsequence using binary
   indexed tree is "<<calcMaxSumBIT(arr, n);
   return 0;
}

出力

The maximum sum increasing subsequence using binary indexed tree is 20