在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解决方法
在此问题中，我们需要通过使用二进制索引树来找到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
热门推荐
10 恩师退休花束祝福语简短
11 怎样给人送祝福语简短
12 苦难的成语祝福语简短
13 女侠老师祝福语简短
14 2026祝福语简短创意牛
15 给儿子祝福语简短霸气
16 兔年祝福语简短100字
17 企业励志拜年祝福语简短
18 英文写结婚祝福语简短