ลำดับย่อยที่เพิ่มขึ้นมีผลรวมสูงสุดด้วย Binary Indexed Tree ในโปรแกรม C++

ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ของจำนวนเต็ม n ตัว ภารกิจของเราคือสร้างโปรแกรมเพื่อหาลำดับย่อยที่เพิ่มขึ้นมีผลรวมสูงสุดโดยใช้ Binary Indexed Tree ใน C++

คำอธิบายปัญหา

เราต้องหาลำดับย่อยที่เพิ่มขึ้นที่มีผลรวมสูงสุดโดยใช้องค์ประกอบของอาร์เรย์

ลำดับย่อยที่เพิ่มขึ้น (Increasing Subsequence)

ลำดับย่อยที่ค่าขององค์ประกอบปัจจุบันมากกว่าองค์ประกอบที่ตำแหน่งก่อนหน้า

Binary Indexed Tree (Fenwick 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

แนวทางแก้ปัญหา

ในปัญหานี้ เราต้องหา maxSum ที่เป็นไปได้โดยใช้ Binary Index Tree สำหรับสิ่งนี้ เราจะสร้าง Binary Index Tree โดยใช้ map จากองค์ประกอบของอาร์เรย์ จากนั้นใช้องค์ประกอบของอาร์เรย์โดยการวนซ้ำ สำหรับแต่ละองค์ประกอบ เราต้องหาผลรวมขององค์ประกอบทั้งหมดจนถึงค่าใน 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