इस समस्या में, हमें 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 समाधान दृष्टिकोण
इस समस्या में, हमें एक बाइनरीइंडेक्स ट्री का उपयोग करके अधिकतम संभव अधिकतम खोजने की आवश्यकता है। इसके लिए, हम सरणी के तत्वों के मानचित्र का उपयोग करके एक बाइनरी इंडेक्स ट्री बनाएंगे। फिर सरणी के तत्वों को पुनरावृत्त करके, foreach तत्व का उपयोग करके हमें बीआईटी में मूल्य तक सभी तत्वों का योग खोजने की आवश्यकता है। और फिर सभी मानों का अधिकतम योग लौटाएं।
उदाहरण
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
#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