在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 生女孩红包简短祝福语
