2 O(n^2) DP solutions. Explanation for people who has difficulty in understanding the DP approach..


  • 3
    K

    I want to share 2 DP solutions for this problem.
    First one came to my mind at first. It is slower but I think it can help people who is new to DP and having difficulty in visualizing it. So I want to share:

    Let's take the array in the problem
    [10, 9, 2, 5, 3, 7, 101, 18]
    For each element we write the elements bigger than it into a list (will form an array of lists)
    10 -> 101,18
    9 -> 101,18
    2 -> 5,3,7,101,18
    5 -> 7,101,18
    3 -> 7,101,18
    7 -> 101,18
    101 -> no element
    18 -> no element since it is the last element

    Then we define our dp array. And dp[len-1] = 1 which stands for 18. It is 1 because 18 is the only element in the subsequence that can be formed since it is the last element.

    We traverse the array reverse and assign each dp element by this way:
    For 101 : there is no element in its list so dp[len-2] = 1
    For 7: There are 18 and 101 in its list so two subsequence alternatives are 7-18 or 7-101. So we see that our dp equation is dp[7] = Max(dp[101],dp[18]) + 1 = 1 + 1 = 2. We add 1 because 7 will also be included in the subsequence (I wrote the numbers in the square brackets for easiness, they are related indexes in fact)
    For 3: dp[3] = Max(dp[7],dp[101],dp[18]) + 1 = 2 + 1 = 3. This means that the subsequence is 3-7-101 or 3-7-18.
    We continue for the remaining elements in the array and when the dp is fulled totally we return the maximum number in the dp:

    Here is the code:

    public class Solution {
        public int LengthOfLIS(int[] nums) {
            
            int len = nums.Length;
            if (len <= 1) return len;
            
            int[] dp = new int[len];
            List<int>[] arrList = new List<int>[len - 1];
            
            for (int i = 0; i < len - 1; i++){
                arrList[i] = new List<int>();
                for (int j  = i + 1; j < len; j++){
                    if (nums[j] > nums[i])
                        arrList[i].Add(j);
                }
            }
            int max = 1;
            dp[len - 1] = 1;
            for (int i = len - 2; i >= 0; i--){
                for (int j = 0; j < arrList[i].Count; j++){
                    dp[i] = Math.Max(dp[i], dp[arrList[i][j]]);
                }
                dp[i]++;
                max = Math.Max(max,dp[i]);
            }
            return max;
        }
    }
    

    This code has the time complexity of O(2(n^2)) which is O(n^2). Its performance is slow (beats 3-4%)

    The faster O(n^2) code is:

    public class Solution {
        public int LengthOfLIS(int[] nums) {
            
            int len = nums.Length;
            if (len <= 1) return len;
            
            int max = 1;
            int[] dp = new int[len];
            dp[0] = 1;
            for (int i = 1; i < len; i++){
                for (int j  = 0; j < i; j++){
                    if (nums[j] < nums[i])
                        dp[i] = Math.Max(dp[i], dp[j]);
                }
                dp[i]++;
                max = Math.Max(max, dp[i]);
            }
    
            return max;
        }
    }
    

    This is faster than the previos one (beats 10-11%). But still slow since there is an O(nlogn) solution for this problem.

    It has been a long post :)
    I hope it helps..


  • 0

    Upvoted for detailed explanation starting from the beginning.


  • 0
    K

    @new2500 Thank you..


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.