Given an array input[] of size ‘N’ with all the integer elements, the task is to find the maximum sum of an increasing subsequence in the array.
Example 1
Input
Input[] = { 4, 6, 2, 5, 8 }
N = 5
Output
18
Explanation
All the increasing subsequences are
4, 6, 8
2, 5, 8
Out of both the increasing subsequences, the maximum sum will be generated by the first subsequence, which is 4 + 6 + 8 = 18, hence the Maximum Sum of Increasing Subsequence in the given input array is 18.
Approach
The approach for this problem is to use Dynamic Programming by creating a DP table to store the result, and the value present at DP[i][j] will depict the maximum sum of any increasing subsequence of length ‘j’ ending at ith index. Any subsequence of length ‘j - 1’ and ending at any of the indexes before the current index can be further extended to the current index by adding the current element’s value to it, and the size will now get changed to j. For any index ‘i’, DP[i][L] will depict the maximum sum that a subsequence of size ‘L’ ending at this index can have. We can get our result or answer by finding the maximum value amongst all DP[i][L] but this approach will cost quadratic time complexity.
We can optimize the solution using the Fenwick tree. The idea to solve this problem is to use the map and Fenwick tree. Make a map containing unique occurring elements and their index value, like for an array { 4, 6, 2, 5, 8 }
4 will be assigned index 0
6 will be assigned index 1
2 will be assigned index 2
5 will be assigned index 3
8 will be assigned index 4
Then using the map, construct Fenwick tree to perform the basic operations. Given below is the detailed algorithm and implementation for the same.
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;
}
Output:
18
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.
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.
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.
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.
38+ registered 