इस समस्या में, हमें n पूर्णांकों की एक सरणी arr[] दी गई है। हमारा कार्य एक प्रोग्राम बनाना है जो C++ में बाइनरी इंडेक्स्ड ट्री का उपयोग करके अधिकतम योग बढ़ता उपअनुक्रम ढूंढे।
समस्या विवरण
हमें सरणी के तत्वों का उपयोग करके एक बढ़ते उपअनुक्रम को ढूंढना है जिसका अधिकतम योग हो।
बढ़ता उपअनुक्रम (Increasing Subsequence)
उपअनुक्रम जिसमें वर्तमान तत्व का मान पिछली स्थिति के तत्व से अधिक होता है।
बाइनरी इंडेक्स्ड ट्री (Binary Indexed Tree)
यह एक डेटा संरचना है जो एक प्रकार का ट्री है। हम ट्री में तत्वों को प्रभावी तरीके से जोड़ या हटा सकते हैं।
उदाहरण
इनपुट
arr[] = {5, 1, 7, 3, 8, 2}
आउटपुट
20
व्याख्या
उपअनुक्रम: {5, 7, 8} = 5 + 7 + 8 = 20
{1, 3, 8} = 1 + 3 + 8 = 12
{1, 7, 8} = 1 + 7 + 8 = 16
समाधान दृष्टिकोण
इस समस्या में, हमें बाइनरी इंडेक्स ट्री का उपयोग करके अधिकतम संभव योग ढूंढना है। इसके लिए, हम सरणी के तत्वों से एक मैप का उपयोग करके बाइनरी इंडेक्स ट्री बनाएंगे। फिर सरणी के तत्वों का उपयोग करके पुनरावृति करके, प्रत्येक तत्व के लिए हमें 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 BinaryIndexTree;
for (int i = 0; i < n; i++) {
BinaryIndexTree[arr[i]] = 0;
}
for (map::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
