Trong bài toán này, chúng ta cho một mảng arr [] gồm n số nguyên. Nhiệm vụ của chúng tôi là tạo ra một chương trình để tìm tổng số tối đa tăng dần con bằng cách sử dụng cây được lập chỉ mục nhị phân trong C ++.
Mô tả sự cố - Chúng ta cần tìm dãy con tăng dần với tổng lớn nhất bằng cách sử dụng các phần tử của mảng.
Tăng thứ tự phụ - dãy con trong đó giá trị của phần tử hiện tại lớn hơn giá trị của phần tử ở vị trí trước đó.
Cây được lập chỉ mục nhị phân - Nó là một cấu trúc dữ liệu là một loại cây. Chúng ta có thể thêm hoặc bớt các phần tử khỏi cây một cách hiệu quả.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
arr[] = {5, 1, 7, 3, 8, 2} Đầu ra
20
Giải thích
Subsequences:
{5, 7, 8} = 5 + 7 + 8 = 20
{1, 3, 8} = 1 + 3 + 8 = 12
{1, 7, 8} = 1 + 7 + 8 = 16 Phương pháp tiếp cận giải pháp
Trong bài toán này, chúng ta cần tìm maxSum có thể bằng cách sử dụng cây binaryindex. Đối với điều này, chúng tôi sẽ tạo một cây chỉ mục nhị phân bằng cách sử dụng một bản đồ từ các thành phần của mảng. Sau đó, sử dụng các phần tử của mảng bằng cách lặp đi lặp lại, trước phần tử, chúng ta cần tìm tổng của tất cả các phần tử cho đến giá trị trong BIT. Và sau đó trả về tổng lớn nhất của tất cả các giá trị.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
#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;
} Đầu ra
The maximum sum increasing subsequence using binary indexed tree is 20