ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ของจำนวนเต็ม n ตัว งานของเราคือสร้างโปรแกรมเพื่อค้นหาผลรวมที่เพิ่มขึ้นตามลำดับโดยใช้ทรีดัชนีไบนารีใน 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 ที่เป็นไปได้โดยใช้ต้นไม้ไบนารีดัชนี สำหรับสิ่งนี้ เราจะสร้างแผนผังดัชนีไบนารีโดยใช้แผนที่จากองค์ประกอบของอาร์เรย์ จากนั้นใช้องค์ประกอบของอาร์เรย์โดยวนซ้ำองค์ประกอบ foreach เราต้องหาผลรวมขององค์ประกอบทั้งหมดจนถึงค่าใน 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
