C++ 中使用二叉索引树求最大和递增子序列
c++server side programmingprogramming
在这个问题中，我们给定一个包含 N 个元素的数组 arr[]。我们的任务是编写一个程序，使用 C++ 中的二叉索引树来查找最大和递增子序列。
让我们举个例子来理解这个问题:
输入
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<<"使用二叉索引树的最大和增加子序列是 "<<maxSumIS(arr, n);
return 0;
}
输出
使用二叉索引树的最大和增加子序列是 19
