이 문제에서는 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 솔루션 접근 방식
이 문제에서는 바이너리 인덱스 트리를 사용하여 가능한 maxSum을 찾아야 합니다. 이를 위해 배열의 요소에서 맵을 사용하여 이진 인덱스 트리를 생성합니다. 그런 다음 요소를 반복하여 배열의 요소를 사용하여 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