[Leetcode] 300. Longest Increasing Subsequence

https://leetcode.com/problems/longest-increasing-subsequence/

불러오는 중입니다...

---

1. Problem 

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

 

 

2. Algorithm

I used dp solution with time complexity O(n^2).

Step 1. Iterate index i 0 to length of array. -> O(n)

Step 2. With index j find the longest length before d[i] iteratively, where nums[i] > nums[j]. -> O(n)

Step 3. After j loop, assign longest length + 1 to d[i] and compare d[i] to len value, save longer length. This step is included in loop i.

At the end, we can get the answer in value 'len'. Return len.

class Solution {
    public int lengthOfLIS(int[] nums) {
        int d[] = new int[nums.length];
        int len = 0;
        for(int i = 0; i < nums.length; i++) {	// Step 1
            if(d[i] == 0) {
                int max = 0;
                for (int j = 0; j < i; j++) 	// Step 2
                    if (nums[i] > nums[j]) max = Math.max(max, d[j]);
                d[i] = max+1;					// Step 3
                len = Math.max(len,d[i]);
            }
        }
        return len;
    }
}

 

 

3. retrospective

Famous problem named LIS. I solved it with DP algorithm, but there is better solution with binary search(nlgn). If you find more faster solution, then I recommend check out the leetcode site.