Algorithm

[LeetCode 300] Longest Increasing Subsequence [Java] [Runtime : 0MS]

顿搜

2017-07-16

0 评论

682 阅读

正在检测是否收录...

07/16

1. Runtime Distribution

2. Submission Details

3. Description

Given an unsorted array of integers, find the length of longest increasing subsequence.
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?

4. Example

Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4

5. Code

import java.util.Arrays;
import org.junit.Test;

public class LeetCode0300 {

    public int lengthOfLIS(int[] nums) {
        int dp[] = new int[nums.length];
        int length = 0;
        for (int i = 0; i < nums.length; i++) {
            int index = Arrays.binarySearch(dp, 0, length, nums[i]);
            if (index < 0) {
                index = -index - 1;
            }
            dp[index] = nums[i];
            if (index == length) {
                length++;
            }
        }
        return length;
    }

    @Test
    public void test() {
        int[] nums = { 10, 9, 2, 5, 3, 7, 101, 18 };
        System.out.println(lengthOfLIS(nums));
    }
}

import org.junit.Test;

public class LeetCode0300 {

    public int lengthOfLIS(int[] nums) {

        int[] dp = new int[nums.length];
        int length = 0;

        for (int i = 0; i < nums.length; i++) {
            if (length == 0 || dp[length - 1] < nums[i]) {
                dp[length] = nums[i];
                length++;
                continue;
            }

            int left = 0, right = length - 1;
            while (left < right) {
                int mid = left + ((right - left) >> 1);
                if (dp[mid] < nums[i]) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            dp[left] = nums[i];

        }
        return length;
    }

    @Test
    public void test() {
        int[] nums = { 10, 9, 2, 5, 3, 7, 101, 18 };
        System.out.println(lengthOfLIS(nums));
    }
}

Binary DP

朗读