Chuỗi con tăng tổng số tối đa bằng cách sử dụng cây được lập chỉ mục nhị phân trong C ++

Trong bài toán này, chúng ta được cung cấp một mảng arr [] gồm N phần tử. Nhiệm vụ của chúng tôi là tạo một chương trình để tìm Chuỗi con tăng tổng tối đa bằng cách sử dụng Cây được lập chỉ mục nhị phân trong C ++.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào

arr[] = {4, 1, 9, 2, 3, 7}

Đầu ra

13

Giải thích

Số con tăng dần tối đa là 1, 2, 3, 7. Tổng =13

Phương pháp tiếp cận giải pháp

Để giải quyết vấn đề, chúng ta sẽ sử dụng Binary Indexed Tree, trong đó chúng ta sẽ chèn các giá trị và ánh xạ chúng thành cây nhị phân được indexed tree. Sau đó tìm giá trị lớn nhất.

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 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;
}

Đầu ra

The Maximum sum increasing subsquence using Binary Indexed Tree is 19