Redirecting to
NADOS


  Prev   Next

Maximum Sum Increasing Subsequence







A goal should scare you a little, and excite you a lot.
~ Joe Vitale

Maximum Sum Increasing Subsequence

Welcome Back Reader!

We hope that you are doing great with Dynamic Programming so far. In this article we will discuss about the next problem based on
"Dynamic Programming" i.e. "Maximum Sum Increasing Subsequence".

We suggest you go through the problem link first, to get an outline of the question.


Important Links : Problem Link, Question Video , Solution Video


Before you move any further, it is advised that you give this problem a fair try.

Let's jump to the problem.

Understanding the problem:

In this problem you are given a number n, representing the number of elements, followed by n numbers, representing the contents of an array of length n.

All you are required to do is print the sum of elements of the increasing subsequence with maximum sum for the array.

For example:

Sample Input: 10 10 22 9 33 21 50 41 60 80 1

Sample Output: 255

How ?

10, 22, 33, 50, 60 and 80 is the increasing subsequence which gives the maximum sum i. e. 255.

For more clarity of the question, watch this part of the video.

Approach:
  • In this problem, we need to print the sum of elements of the increasing subsequence with the maximum sum of the array.
  • To solve this problem, we will use an array, dp, which at any index 'i' will store the maximum sum till arr[i] (arr being input array) of all the possible increasing subsequences. Consider the following example: 10 10 22 9 33 21 50 41 60 80 1
  • First of all we need a dp array of length 10.
  • Then using a 'for' loop, we will fill this dp array.
    • img
  • With the help of dp filled so far, find a value so that the current value can be the part of the increasing subsequence. Like, while filling the dp corresponding to '41', start checking from dp[0].
  • First of all we check that if 10 is smaller than 41, as it is smaller therefore we will store 10 in the current max value.
  • Next moving to 22, check if 22 is smaller than 41, yes it is so update max with 32.
  • Next moving to 9, check if 9 is smaller than 41, yes it is but 9 is not greater than the current max which is 32. So we will move to the next element without updating max.
  • Next element is 33, and 33 is smaller than 41, and its corresponding dp value i.e. 65 is greater than 32. So we will update max with 65.
  • Next moving to 21, check if 21 is smaller than 41, yes it is but 31 is not greater than current max which is 65. So we will move to the next element without updating max.
  • Next element is 50, and 50 is not smaller than 41, so there is need to process this further as the property of increasing subsequence has already been violated.
  • So the traversal before 41 has been completed. Now we will add 41 to the current max value i. e. 65. And the new value becomes 106. So we will store 106 in dp corresponding to 41.
  • After doing this part, check the omax, if omax is greater than this dp then update omax with this dp otherwise skip it. In this case omax is 115 and dp is 106 so omax will not be updated.

    • For more clarity of this part, watch this part of the video.

    Let's try to code this!

    img
  • To start with, define a variable 'omax' of type 'int' and initialize it to Integer.Min VALUE. Also define an array of length same as that of input array.
  • Then to fill the dp array, apply a for loop on the dp array's length. On entering this loop, define a variable 'max' and initialize it to null.
  • Now to fill the dp[i] we need to get the maximum sum of all the possible increasing subsequences so far such that the current element can be part of this subsequence.

    • To do this we will use a 'for' loop from 0 to (i-1) to get the maximum sum stored at dp[j], when arr[i]=>arr[j].

  • While doing this, to keep track of maximum sum, we will store the dp[j] in max and before doing so also make sure that previous stored value in max is greater than dp[j].
  • After getting max using for loop, first of all check if max is null or not. If it's not null then you can put max + arr[i] at dp[i]. But if it's null then simply put arr[i] at dp[i].
  • To get the overall max, check if dp[i] is greater than omax and if it is then update omax with dp[i].
  • At last print omax.

    • For more clarity of the code, watch this part of the video.

Complexities:
Time Complexity: O(n^2)

A nested 'for' loop has been used, making the time complexity O(n^2).

Space Complexity: O(n)

Since an array of n length has been used, therefore the space complexity becomes O(n).

Complete Code:

import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); int[] arr = new int[n]; for (int i = 0; i < arr.length; i++) { arr[i] = Integer.parseInt(br.readLine()); } int omax = Integer.MIN_VALUE; int[] dp = new int[arr.length]; for(int i = 0; i < arr.length; i++){ Integer max = null; for(int j = 0; j < i; j++){ if(arr[j] <= arr[i]){ if(max == null || dp[j] > max){ max = dp[j]; } } } if(max != null){ dp[i] = max + arr[i]; } else { dp[i] = arr[i]; } if(dp[i] > omax){ omax = dp[i]; } } System.out.println(omax); } }
java; true";
We hope that this article was helpful. If somehow you are finding it difficult to understand this problem then we advise you to watch our video lecture of this problem.

Trust me it will just get easier to understand after you have watched the solution video.

You can contact us via our website. Doubts, suggestions and feedback are always welcomed.
It is also advised that you follow the sequence of modules and questions which is there on our website.

Keep practicing more and more problems daily. Meditate enough on each step of each problem.

All the best for an exciting future!
Happy Coding!

Arrays
Dynamic Programming
Author: Nikita Aggarwal
 
Run
Id Name