Maximum Sum of Increasing Subsequence using Fenwick Tree

Algorithm

• The first step is to put all of the data in a map, and then we can map these array values to the Fenwick Tree's indexes.
• Iterate the map and assign indexes. 
• Construct the Fenwick tree
• For every value in the given array perform the following steps
  • Find the maximum sum till that position using Fenwick Tree
  • Update the Fenwick Tree with New Maximum Value
• Returns the maximum sum which is present at the last position of Fenwick Tree. 

Code:

// Maximum Sum of Increasing Subsequence
#include <bits/stdc++.h>
using namespace std;

// Returns the maximum sum value of the increasing subsequence till that current index
int getMaxSum(int FenwickTree[], int currindex)
{
    int sum = 0;
    while (currindex > 0) {
        sum = max(sum, FenwickTree[currindex]);
        currindex -= currindex & (-currindex);
    }
    return sum;
}

/* 
    Updates a node in Fenwick tree at given index in
    fenwick tree The maximum value is updated
    by taking maximum of val and the
    already present value in the node.
*/
void updateTree(int FenwickTree[], int index,int currindex, int val)
{
    while (currindex <= index) {
        FenwickTree[currindex] = max(val, FenwickTree[currindex]);
        currindex += currindex & (-currindex);
    }
}

// Returns the maximum sum of increasing subsequence
int maxsumIncreasingSubsequence(int input[], int N)
{
    int index = 0, maxSum;

    map<int, int> m;

    // Inserting all values in map m
    for (int i = 0; i < N; i++) {
        m[input[i]] = 0;
    }

    // Assigning indexes to the map values
    for (auto it : m ) {

        // index is maintaining the count of unique values
        index++;
        m[it.first] = index;
    }

    // Constructing the FenwickTree
    int* FenwickTree = new int[index + 1];

    // Initializing the FenwickTree
    for (int i = 0; i <= index; i++) {
        FenwickTree[i] = 0;
    }

    for (int i = 0; i < N; i++) {

        // Finding maximum sum till this element
        maxSum =  getMaxSum(FenwickTree, m[input[i]] - 1);

        // Updating the BIT with new maximum sum
        updateTree(FenwickTree, index,m[input[i]], maxSum + input[i]);
    }

    // Return maximum sum
    return getMaxSum(FenwickTree, index);
}

int main()
{
    int input[] = { 4,6,2,5,8  };
    int N = sizeof(input) / sizeof(input[0]);

    // Finding Maximum Sum of Increasing Subsequence
    cout << maxsumIncreasingSubsequence(input, N);

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

18 You can also try this code with Online C++ Compiler Run Code

Time Complexity 

O(N * log(N))

The time complexity to find  Maximum Sum of Increasing Subsequence using Fenwick Tree is O(N * log(N)), where 'N' is the size of the input Array. Since we are creating an extra array to store the elements in the form of a Fenwick tree, iterating in the Fenwick tree will only cost log(N) time, where 'N' represents a total number of nodes in the tree. The time complexity for the construction of the Fenwick tree is O(N * log(N)). Since we are updating to ‘N’ elements hence the total time complexity is O(N * log(N)).

Space Complexity 

O(N)

The space complexity to find the Maximum Sum of Increasing Subsequence using Fenwick Tree is O(N), where ‘N’ is the size of the input Array since we are creating an extra array to store the elements in the form of a Fenwick tree.

Check out this problem - Subarray With 0 Sum

Check out this : Longest common subsequence

FAQs

1. What are Fenwick trees?
   A Fenwick tree, also known as a binary indexed tree, is a data structure that can quickly update items in a table of numbers and calculate prefix sums.
    
2. Where are Fenwick trees used?
   A Fenwick tree helps in the computation of prefix sums. Prefix sums are frequently used in a variety of other algorithms, as well as in a number of competitive programming contests. , For example, They're utilized to implement the arithmetic coding algorithm.
    
3. How the Fenwick tree is making the solution more effective?
   Fenwick tree uses the concept of bits. Least-significant-bit operation is used in the Fenwick tree array to compute the results of the prefix array which can be calculated in logarithmic time.

Key Takeaways

In this blog, we discussed the solution for finding the Maximum Sum of Increasing Subsequence using the Fenwick Tree; the article also focused on the time and space complexity of the solution.

If you want to learn more about the Fenwick trees and want to practice some quality questions which require you to excel your preparation a notch higher, then you can visit our Guided Path for Fenwick tree on Coding Ninjas Studio.To be more confident in data structures and algorithms, try out our DS and Algo Course. Until then, All the best for your future endeavors, and Keep Coding.