Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: [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. 

Note:

  • There may be more than one LIS combination, it is only necessary for you to return the length.
  • Your algorithm should run in O(n2) complexity.

Solution

public class Solution {
    public int LengthOfLIS(int[] nums) {
        
        if(nums == null || nums.Length == 0)
            return 0;
        
        int[] LIS = Enumerable.Repeat(1,nums.Length).ToArray();
        
        for(int i=0;i<nums.Length;i++)
        {
            for(int j=0;j<i;j++)
            {
                if(nums[i] > nums[j] && LIS[i] <= LIS[j])
                {
                    LIS[i] = 1 + LIS[j];                   
                }
            }
        }
        
        //Find Max
        int max = LIS[0];
        for(int i=1;i<LIS.Length;i++)
            max = Math.Max(LIS[i],max);
        
        return max;
        
    }
}

Time Complexity: O(n*n)

Space Complexity: O(n)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s