在C ++中使用二进制索引树的最大总和增加子序列
在这个问题中，我们给了N个元素的数组arr[]。我们的任务是创建一个程序，以使用C++中的二进制索引树来找到最大的Sum递增子序列。
让我们举个例子来了解这个问题，
输入项
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
热门推荐
10 香港老妈结婚祝福语简短
11 毕业立体贺卡祝福语简短
12 简短新年年会祝福语
13 评论小品祝福语大全简短
14 恭喜师兄结婚祝福语简短
15 员工集体辞职祝福语简短
16 高中新生祝福语 简短
17 装修祝福语男生搞笑简短
18 生日开业蛋糕祝福语简短