Given an array of size n. Find the maximum sum of an increasing subsequence.
Examples:
Input : arr[] = { 1, 20, 4, 2, 5 }
Output : Maximum sum of increasing subsequence is = 21
The subsequence 1, 20 gives maximum sum which is 21
Input : arr[] = { 4, 2, 3, 1, 5, 8 }
Output : Maximum sum of increasing subsequence is = 18
The subsequence 2, 3, 5, 8 gives maximum sum which is 18
Prerequisite
The solution makes the use of Binary Indexed Tree and map.
Dynamic Programming Approach: DP approach which is in O(n^2) .
Solution
Step 1 :
The first step is to insert all values in a map, later we can map these array values to the indexes of Binary Indexed Tree.
Step 2 :
Iterate the map and assign indexes. What this would do is for an array { 4, 2, 3, 8, 5, 2 }
2 will be assigned index 1
3 will be assigned index 2
4 will be assigned index 3
5 will be assigned index 4
8 will be assigned index 5
Step 3 :
Construct the Binary Indexed Tree.
Step 4 :
For every value in the given array do the following.
Find the maximum sum till that position using BIT and then update the BIT with New Maximum Value
Step 5 :
Returns the maximum sum which is present at last position in Binary Indexed Tree.
C++
// C++ code for Maximum Sum// Increasing Subsequence#include <bits/stdc++.h>using namespace std;// Returns the maximum value of// the increasing subsequence// till that index// Link to understand getSum functionint getSum(int BITree[], int index){ int sum = 0; while (index > 0) { sum = max(sum, BITree[index]); index -= index & (-index); } return sum;}// Updates a node in Binary Index// Tree (BITree) at given index in// BITree. The max value is updated// by taking max of 'val' and the// already present value in the node.void updateBIT(int BITree[], int newIndex, int index, int val){ while (index <= newIndex) { BITree[index] = max(val, BITree[index]); index += index & (-index); }}// maxSumIS() returns the maximum// sum of increasing subsequence// in arr[] of size nint maxSumIS(int arr[], int n){ int newindex = 0, max_sum; map<int, int> uniqueArr; // Inserting all values in map uniqueArr for (int i = 0; i < n; i++) { uniqueArr[arr[i]] = 0; } // Assigning indexes to all // the values present in map for (map<int, int>::iterator it = uniqueArr.begin(); it != uniqueArr.end(); it++) { // newIndex is actually the count of // unique values in the array. newindex++; uniqueArr[it->first] = newindex; } // Constructing the BIT int* BITree = new int[newindex + 1]; // Initializing the BIT for (int i = 0; i <= newindex; i++) { BITree[i] = 0; } for (int i = 0; i < n; i++) { // Finding maximum sum till this element max_sum = getSum(BITree, uniqueArr[arr[i]] - 1); // Updating the BIT with new maximum sum updateBIT(BITree, newindex, uniqueArr[arr[i]], max_sum + arr[i]); } // return maximum sum return getSum(BITree, newindex);}// Driver programint main(){ int arr[] = { 1, 101, 2, 3, 100, 4, 5 }; int n = sizeof(arr) / sizeof(arr[0]); cout << "Maximum sum is = " << maxSumIS(arr, n); return 0;} |
Java
// JAVA code for Maximum Sum// Increasing Subsequenceimport java.util.*;class GFG{// Returns the maximum value of// the increasing subsequence// till that index// Link to understand getSum function// binary-indexed-tree-or-fenwick-tree-2/static int getSum(int BITree[], int index){ int sum = 0; while (index > 0) { sum = Math.max(sum, BITree[index]); index -= index & (-index); } return sum;}// Updates a node in Binary Index// Tree (BITree) at given index in// BITree. The max value is updated// by taking max of 'val' and the// already present value in the node.static void updateBIT(int BITree[], int newIndex, int index, int val){ while (index <= newIndex) { BITree[index] = Math.max(val, BITree[index]); index += index & (-index); }}// maxSumIS() returns the maximum// sum of increasing subsequence// in arr[] of size nstatic int maxSumIS(int arr[], int n){ int newindex = 0, max_sum; HashMap<Integer, Integer> uniqueArr = new HashMap<>(); // Inserting all values in map // uniqueArr for (int i = 0; i < n; i++) { uniqueArr.put(arr[i], 0); } // Assigning indexes to all // the values present in map for (Map.Entry<Integer, Integer> entry : uniqueArr.entrySet()) { // newIndex is actually the // count of unique values in // the array. newindex++; uniqueArr.put(entry.getKey(), newindex); } // Constructing the BIT int []BITree = new int[newindex + 1]; // Initializing the BIT for (int i = 0; i <= newindex; i++) { BITree[i] = 0; } for (int i = 0; i < n; i++) { // Finding maximum sum till // this element max_sum = getSum(BITree, uniqueArr.get(arr[i]) - 3); // Updating the BIT with // new maximum sum updateBIT(BITree, newindex, uniqueArr.get(arr[i]), max_sum + arr[i]); } // return maximum sum return getSum(BITree, newindex);}// Driver programpublic static void main(String[] args){ int arr[] = {1, 101, 2, 3, 100, 4, 5}; int n = arr.length; System.out.print("Maximum sum is = " + maxSumIS(arr, n));}}// This code is contributed by shikhasingrajput |
C#
// C# code for Maximum Sum// Increasing Subsequenceusing System;using System.Collections.Generic;class GFG{// Returns the maximum value of// the increasing subsequence// till that index// Link to understand getSum function// binary-indexed-tree-or-fenwick-tree-2/static int getSum(int []BITree, int index){ int sum = 0; while (index > 0) { sum = Math.Max(sum, BITree[index]); index -= index & (-index); } return sum;}// Updates a node in Binary Index// Tree (BITree) at given index in// BITree. The max value is updated// by taking max of 'val' and the// already present value in the node.static void updateBIT(int []BITree, int newIndex, int index, int val){ while (index <= newIndex) { BITree[index] = Math.Max(val, BITree[index]); index += index & (-index); }}// maxSumIS() returns the maximum// sum of increasing subsequence// in []arr of size nstatic int maxSumIS(int []arr, int n){ int newindex = 0, max_sum; Dictionary<int, int> uniqueArr = new Dictionary<int, int>(); // Inserting all values in map // uniqueArr for (int i = 0; i < n; i++) { uniqueArr.Add(arr[i], 0); } Dictionary<int, int> uniqueArr1 = new Dictionary<int, int>(); // Assigning indexes to all // the values present in map foreach (KeyValuePair<int, int> entry in uniqueArr) { // newIndex is actually the // count of unique values in // the array. newindex++; if(uniqueArr1.ContainsKey(entry.Key)) uniqueArr1[entry.Key] = newindex; else uniqueArr1.Add(entry.Key, newindex); } // Constructing the BIT int []BITree = new int[newindex + 1]; // Initializing the BIT for (int i = 0; i <= newindex; i++) { BITree[i] = 0; } for (int i = 0; i < n; i++) { // Finding maximum sum till // this element max_sum = getSum(BITree, uniqueArr1[arr[i]] - 4); // Updating the BIT with // new maximum sum updateBIT(BITree, newindex, uniqueArr1[arr[i]], max_sum + arr[i]); } // return maximum sum return getSum(BITree, newindex);}// Driver programpublic static void Main(String[] args){ int []arr = {1, 101, 2, 3, 100, 4, 5}; int n = arr.Length; Console.Write("Maximum sum is = " + maxSumIS(arr, n));}}// This code is contributed by shikhasingrajput |
Javascript
<script>// JavaScript code for Maximum Sum// Increasing Subsequence// Returns the maximum value of// the increasing subsequence// till that index// Link to understand getSum function// binary-indexed-tree-or-fenwick-tree-2/function getSum(BITree, index){ var sum = 0; while (index > 0) { sum = Math.max(sum, BITree[index]); index -= index & (-index); } return sum;}// Updates a node in Binary Index// Tree (BITree) at given index in// BITree. The max value is updated// by taking max of 'val' and the// already present value in the node.function updateBIT(BITree, newIndex, index, val){ while (index <= newIndex) { BITree[index] = Math.max(val, BITree[index]); index += index & (-index); }}// maxSumIS() returns the maximum// sum of increasing subsequence// in []arr of size nfunction maxSumIS(arr, n){ var newindex = 0, max_sum; var uniqueArr = new Map(); // Inserting all values in map // uniqueArr for (var i = 0; i < n; i++) { uniqueArr.set(arr[i], 0); } var uniqueArr1 = new Map(); // Assigning indexes to all // the values present in map uniqueArr.forEach((value, key) => { // newIndex is actually the // count of unique values in // the array. newindex++; uniqueArr1.set(key, newindex); }); // Constructing the BIT var BITree = Array(newindex+1).fill(0); for (var i = 0; i < n; i++) { // Finding maximum sum till // this element max_sum = getSum(BITree, uniqueArr1.get(arr[i]) - 4); // Updating the BIT with // new maximum sum updateBIT(BITree, newindex, uniqueArr1.get(arr[i]), max_sum + arr[i]); } // return maximum sum return getSum(BITree, newindex);}// Driver programvar arr = [1, 101, 2, 3, 100, 4, 5];var n = arr.length;document.write("Maximum sum is = " + maxSumIS(arr, n));</script> |
Python3
# python code for Maximum Sum# Increasing Subsequence# Returns the maximum value of# the increasing subsequence# till that index# Link to understand getSum functiondef getSum(BITree, index): sum = 0 while (index > 0): sum = max(sum, BITree[index]) index -= index & (-index) return sum# Updates a node in Binary Index# Tree (BITree) at given index in# BITree. The max value is updated# by taking max of 'val' and the# already present value in the node.def updateBIT(BITree, newIndex, index, val): while (index <= newIndex): BITree[index] = max(val, BITree[index]) index += index & (-index)# maxSumIS() returns the maximum# sum of increasing subsequence# in arr[] of size ndef maxSumIS(arr, n): newindex = 0 max_sum = 0 uniqueArr = {} # Inserting all values in map uniqueArr for i in range(0, n): uniqueArr[arr[i]] = 0 # Assigning indexes to all # the values present in map for it in sorted(uniqueArr): # newIndex is actually the count of # unique values in the array. newindex += 1 uniqueArr[it] = newindex # Constructing the BIT BITree = [0]*(newindex + 1) # Initializing the BIT for i in range(0, newindex+1): BITree[i] = 0 for i in range(0, n): # Finding maximum sum till this element max_sum = getSum(BITree, uniqueArr[arr[i]] - 1) # Updating the BIT with new maximum sum updateBIT(BITree, newindex, uniqueArr[arr[i]], max_sum + arr[i]) # return maximum sum return getSum(BITree, newindex)# Driver programarr = [1, 101, 2, 3, 100, 4, 5]n = len(arr)print("Maximum sum is = ", maxSumIS(arr, n))# This code is contributed by rj13to. |
Output
Maximum sum is = 106
Note
Time Complexity of the solution
O(nLogn) for the map and O(nLogn) for updating and getting sum. So overall complexity is still O(nLogn).
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
