Given an array of n positive integers. Write a program to find the sum of maximum sum subsequence of the given array such that the integers in the subsequence are sorted in increasing order.
Examples :
Input : [1, 101, 2, 3, 100, 4, 5] Output : 106 Input : [3, 4, 5, 10] Output : 22
Solution :
This problem is a variation of standard Longest Increasing Subsequence (LIS) problem. We need a slight change in the Dynamic Programming solution of LIS problem. All we need to change is to use sum as a criteria instead of length of increasing subsequence. The recurrence relation will be following : DP[i] = max(A[i], A[i] + DP[j]) such that j < i and A[j] < A[i]. It can be done with the help of two loops but the time complexity would be O(n^2). How can we do this in a more efficient way. This solution can be made efficient by using an Advanced Data Structure like Segment Tree or Fenwick Tree (Binary Indexed Tree). By using one of these Data Structure following operations can be done efficiently :
1) Updating the index i.
2) Finding the maximum element in the interval 1 to i.
Consider that arr[1], arr[2], arr[3], …, arr[n] is sorted. We define B[i] as the position of arr[i]. Now to fill DP[i] we find the maximum in the interval [1, B[i]) in segment and we call it x and we set the B[i] th index of the segment as A[i] + x. The answer to the problem would the maximum in the segment in the interval [1, n].
C++ code to solve this problem is given below.
Implementation :
#include<bits/stdc++.h>
using namespace std;
/* Function to update the Fenwick Tree */
void update(int BIT[] ,int n ,int index ,int val)
{
while(index <= n)
{
BIT[index] = max(BIT[index] ,val);
index += (index & -index);
}
}
/* Function to find the maximum in a range */
int query(int BIT[] ,int index)
{
int ret=0;
while(index > 0)
{
ret=max(ret ,BIT[index]);
index -= (index & -index);
}
return ret;
}
/* Function which returns the Maximum sum increasing subsequence */
int maxSumIS(int arr[],int n)
{
/* Array which will store all the elements of the original array in sorted order */
int b[n];
/* Array will represent the Fenwick Tree */
int BIT[100001];
/* Initialising all the nodes of the Tree with 0 */
memset(BIT ,0 ,sizeof(BIT));
int val ,ret = INT_MIN ,maximum ,index;
for(int i = 0;i < n ;i++)
{
b[i] = arr[i];
}
/* Sorting all the elements of the array */
sort(b, b + n);
for(int i = 0; i < n; i++)
{
/* Determining the index of arr[i] by Binary Search */
index = 1 + lower_bound(b ,b + n, arr[i]) - b;
/* Querying for the maximum element in the range 1 to index - 1 */
maximum = query(BIT ,index - 1);
val = arr[i] + maximum;
ret = max(ret ,val);
/* Updating the index */
update(BIT ,n ,index ,val);
}
return ret;
}
int main()
{
int arr[] = { 1, 101, 2, 3, 100, 4, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("Sum of maximum sum increasing subsequence is %d\n",
maxSumIS(arr, n));
return 0;
}
Output : Sum of maximum sum increasing subsequence is 106
Time Complexity : O(n * log n)
