300. Longest Increasing Subsequence

Question

A good way to master coding challenges is to recognize patterns. A good way to recognize patterns is to understand the basics. This may involve understanding one core problem and learning to apply it. Think of it as similar to learning to crawl before learning to walk and then learning to run. An example core problem is the Longest Increasing Subsequence. Variations of this problem are frequently asked. Follow me here, on Twitter, LinkedIn or Github for more.

Problem

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

Constraints:

1 <= nums.length <= 2500
-104 <= nums[i] <= 104

Discussion

To solve, we use dynamic programming. We build a 1-dimensional array lengths to store the maximum length of the subsequences at each index and initialize it so that each value is 1.
Then we use two for loops. The first starts at the second index (index 1 in some programming languages) and iterates forward until the end of the array. We shall refer to it as i .
The second starts at the first index (index 0 in some languages) and iterates forward until it reaches i. We shall refer to it as j. If the number found at j is less than that found at i and lengths[i] is less than or equal to lengths[j], we recalculate the value at lengths[i] as lengths[i]=lengths[j]+1.
On finishing the double for loop,we sort lengths and return the last value which is the largest.

Solution

Java

class Solution {
    public int lengthOfLIS(int[] nums) {
     int [] lengths= new int[nums.length];
     for(int i=0;i<lengths.length;i++)lengths[i]=1;
     for(int i=1;i<nums.length;i++){
      for(int j=0;j<i;j++){
       if(nums[j]<nums[i] && lengths[i]<=lengths[j]) lengths[i]=lengths[j]+1;
      }
     }
     Arrays.sort(lengths);
     return lengths[lengths.length-1];
    }
}

C#

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

C++

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
     vector<int>lengths;
     int max=0;
     for(int i=0;i<nums.size();i++)lengths.push_back(1);
     for(int i=1;i<nums.size();i++){
      for(int j=0;j<i;j++){
       if(nums.at(j)<nums.at(i) && lengths.at(i)<=lengths.at(j)) lengths.at(i)=lengths.at(j)+1;
      }
     }
     for(int i=0;i<lengths.size();i++)max=std::max(max,lengths.at(i)); 
     return max;   
    }
};

Javascript

var lengthOfLIS = function(nums) {
 const lengths= [];
 let max=0;
 for(let i=0;i<nums.length;i++)lengths.push(1);
 for(let i=1;i<nums.length;i++){
  for(let j=0;j<i;j++){
   if(nums[j]<nums[i] && lengths[i]<=lengths[j]) lengths[i]=lengths[j]+1;
  }
 }
 for(let i=0;i<lengths.length;i++)max=Math.max(lengths[i],max);
 return max;
};