在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 金店立秋祝福语简短英文
18 婆婆高寿祝福语大全简短