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

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

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

入力

arr[] = {4, 1, 9, 2, 3, 7}

出力

13

説明

最大増加部分列は1、2、3、7です。合計=13

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

この問題を解決するために、値を挿入してバイナリインデックスツリーにマップするバイナリインデックスツリーを使用します。次に、最大値を見つけます。

例

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

#include <bits/stdc++.h>
using namespace std;
int calcMaxSum(int BITree[], int index){
   int maxSum = 0;
   while (index > 0){
      maxSum = max(maxSum, BITree[index]);
      index -= index & (-index);
   }
   return maxSum;
}
void updateBIT(int BITree[], int newIndex, int index, int val){
   while (index <= newIndex){
      BITree[index] = max(val, BITree[index]);
      index += index & (-index);
   }
}
int maxSumIS(int arr[], int n){
   int index = 0, maxSum;
   map<int, int> arrMap;
   for (int i = 0; i < n; i++){
      arrMap[arr[i]] = 0;
   }
   for (map<int, int>::iterator it = arrMap.begin(); it != arrMap.end(); it++){
      index++;
      arrMap[it->first] = index;
   }
   int* BITree = new int[index + 1];
   for (int i = 0; i <= index; i++){
      BITree[i] = 0;
   }
   for (int i = 0; i < n; i++){
      maxSum = calcMaxSum(BITree, arrMap[arr[i]] - 1);
      updateBIT(BITree, index, arrMap[arr[i]], maxSum + arr[i]);
   }
   return calcMaxSum(BITree, index);
}
int main() {
   int arr[] = {4, 6, 1, 9, 2, 3, 5, 8};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"The Maximum sum increasing subsequence using Binary Indexed Tree is "<<maxSumIS(arr, n);
   return 0;
}

出力

The Maximum sum increasing subsquence using Binary Indexed Tree is 19