資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究使用 C++ 中的二進位制索引樹查詢最大和遞增子序列
本題目中，給定一個包含 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<<"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
更新於：2020 年 10 月 15 日
96 次瀏覽
廣告