資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學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
更新於：2020年12月9日
103次瀏覽
廣告