300. Longest Increasing Subsequence (Medium)

https://leetcode.com/problems/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.

Follow up: Could you improve it to O(n log n) time complexity?

Solutions

1.

class Solution {

    // This solution is a much easier one to understand. The key idea is to make use of dynamic programming.

    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int len = nums.length;

        int[] track = new int[len + 1];
        Arrays.fill(track, 1);

        for (int i = len - 1; i >= 0; i--) {

            // for ith element, pick the proper subsequent element from (i+1)th to (len-1)th
            for (int j = i + 1; j < len; j++) {

                // see if meet the condition that requires increasing order
                if (nums[i] >= nums[j]) {
                    continue;
                }

                track[i] = Math.max(track[i], track[j] + 1);
            }
        }

        int max = 0;
        for (int i = 0; i < len; i++) {
            max = Math.max(max, track[i]);
        }

        return max;
    }
}

2.

class Solution {

    // This solution is a little bit tedious and trivial. It's strongly advised to adopt the
    // Solution instead of this one.

    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int len = nums.length;

        int[] track = new int[len+1];
        Arrays.fill(track, 0);

        recurse(nums, 0, track);

        int max = 0;
        for (int i = 0; i < len; i++) {
            max = Math.max(max, track[i]);
        }

        return max;
    }

    private int recurse(int[] nums, int depth, int[] track) {
        int len = nums.length;

        if (depth >= len) {
            return 0;
        }

        if (track[depth] > 0) {
            return track[depth];
        }

        int max = 1;
        for (int i = depth + 1; i < len; i++) {
            int rst = recurse(nums, i, track);

            // Do not place following condition statements in front of recurse. Otherwise
            // it only search for best subset that contains nums[0]
            if (nums[depth] >= nums[i]) {
                continue;
            }

            max = Math.max(max, rst + 1);
        }

        track[depth] = max;

        return max;
    }
}

Incorrect Solutions

References

Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2020-03-21 22:44:31

results matching ""

    No results matching ""