Longest Increasing Subsequence. Blind 75. Dynamic Programming.

Given an integer array nums, return the length of the longest strictly increasing 

subsequence

Example 1:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Example 2:

Input: nums = [0,1,0,3,2,3]
Output: 4

Example 3:

Input: nums = [7,7,7,7,7,7,7]
Output: 1

Let's first conclude what we can from the question:

1. We need to find longest increasing subsequence
2. At each point the answer if 1, even if we don't calculate anything
3. How can we calculate LCS?
4. Do we need to iterate over the array?
5. How many values we need to compare?
6. we need to compare two values
7. if leftValue < rightValue we know it adds up to the answer
8. Do we need a variable to store the answer?
9. do we need an array? to store our calculation?
10. or do we just need 1 single max value i.e longest increasing subsequent.

What are some application of longest-increasing-subsequence in the Real world?

1. New Feed:
2. Deciding the order of the post based on engagement metrics i.e increasing engagement rate. which can be suggested to new user that will help increase the retention rate.
3. E-commerce: Recommendation Systems
4. Sequence of product views or purchased can be used to suggest/recommed next product to user
5. Google Photos: When creating a movie, or slideshow. longest increasing subsequence based on timestamps or location or other factor can be used.
6. Netflix: Content Sequencing

1. A user watched movie A, B, and then C.
2. Now Netflix want to provide optimal order of content to user.
3. Now Netflix want's to recommend D, E and F sequence to that user.
4. The goal is to maximize the likelihood that user will watch and (enjoy) the suggested movies.
5. To determine the best sequence, Netflix might consider:

Historical data: Which sequences of movies have other similar users enjoyed most?

     comparing left element to the right element.
     if(input[left] < input[right]){
        // we update the value of currentComaprision position of longestIncreasingSubsequence
        // we update the max
     }

To find the length of the LIS, we need to consider the previous elements in the array and their contributions to the increasing subsequence

how do we know this? we can have an array, named dp that will give us the contribution to the increasing subsequence

if at any point,

1. element[left] < elment[right], we can say LIS @ right is atleast LIS @ left + 1
2. if element @ right is greater than element @ left, right moves forward

else

1. we do nothing to
2. we increment left by 1

if @ any point left meets right

1. we reset the loop
2. left starts @ 0
3. right starts where it was + 1

/*

we will use two pointers and compare the value

1. if nums[l] < nums[r]

a.dp[r] = dp[r] + 1

b. else we will just keep on the loop

2. Also we will need two loops to compare between two numbers

*/

var lengthOfLIS = function(nums) {
    const dp = new Array(nums.length).fill(1)
    let max = 1
     for(let left = 0; left < nums.length; left++){
        for(let right = left + 1; right < nums.length; right++ ){
            if(nums[left] < nums[right]){
                dp[right] = Math.max(dp[right] , dp[left] + 1)
                max = Math.max(max, dp[right])
            }
        }
     }
     return max
};

Submitting to the leetcode:

Complexities:

Space Complexity: O(N), N is the length of the array

Time Complexity: O(N^2),