Tuesday, April 26, 2016

Longest Increasing Subsequence

Leetcode 300
Longest Increasing Subsequence
Given an unsorted array of integers, find the length of longest increasing subsequence.
For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that 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.
Follow up: Could you improve it to O(n log n) time complexity?
O(n^2):
Naive solution is use array T[] to track the LIS for each element in the original array. We have to track all the elements because the LIS can only increase for previous element which are smaller than current element.
public class Solution {
    public int lengthOfLIS(int[] nums) {
        // naive solution, keep another array to store the LIS so far. O(n^2)
        if (nums==null || nums.length == 0) return 0;
        int[] lens = new int[nums.length];
        int maxsofar = 1;
        for (int i = 0; i < nums.length; i++) {
            lens[i] = 1;
        }
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    if ((lens[j]+1) > lens[i]) {
                        lens[i] = lens[j] + 1;
                    }
                }
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (lens[i] > maxsofar) maxsofar = lens[i];
        }
        return maxsofar;
    }
}

No comments:

Post a Comment