在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 媳妇生日简短祝福语朋友
15 公司年会祝福语简短最好
16 元旦感恩祝福语简短大全
17 红包祝福语简短10字
18 周六早晨祝福语简短