在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 儿童毕业祝福语 简短6
14 开工仪式横幅祝福语简短
15 孩子日常祝福语大全简短
16 清晨寄语诗句祝福语简短
17 结婚送亲认亲祝福语简短
18 虎年喝酒拜年祝福语简短