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

For example,

Given

The longest increasing subsequence is

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?**Understand the problem:**

A sequence DP problem.

-- dp[n + 1], where dp[i] means the length of the LIS,

**including the ith character.**

-- Initial state: dp[0] = 0, dp[i] = 1, i >= 1

-- Transit function: for j from [0, i), if (nums[i - 1] > nums[j - 1]), dp[i] = Math.max(dp[i], dp[j] + 1);

-- Final state: the max in dp[i].

**Code (Java):**

public class Solution { public int lengthOfLIS(int[] nums) { if (nums == null || nums.length == 0) { return 0; } int[] dp = new int[nums.length + 1]; for (int i = 1; i < nums.length + 1; i++) { dp[i] = 1; } int maxLen = 1; for (int i = 1; i <= nums.length; i++) { for (int j = 1; j < i; j++) { if (nums[i - 1] > nums[j - 1]) { dp[i] = Math.max(dp[i], dp[j] + 1); } } maxLen = Math.max(maxLen, dp[i]); } return maxLen; } }

**Follow-up: Could you solve it in O(nlogn) time?**

**https://leetcode.com/discuss/67609/short-java-solution-using-dp-o-n-log-n**

## No comments:

## Post a Comment