Online C++ Compiler

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