p300

发表于 | 分类于 |

LeetCode p300 Longest Increasing Subsequence 题解

1.题目：

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?

题意：

这道题的意思是，给你一个数组，求出他的最长递增子序列（不一定连续）的长度。

2.解题思路:

dp 。。把思路翻译成白话文应该是这样的。设置一个dp数组用于记录，从数组的第二个数开始往后。
每次将这个数前面的数都检查一遍，看有没有数小于他，而且他的dp数小于查找到数的dp数加1。
则更新dp数组。
遍历完成之后再选取最大值。

3.代码

[title] [] [url] [link text]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
public class Solution {
    public int lengthOfLIS(int[] nums) {
        int ans = 0;
		int len = nums.length;
		int[] dp = new int[len];
		if (nums == null || nums.length < 1)
			return 0;
		for (int i = 1; i < len; i++) {
			for (int j = i - 1; j >= 0; j--) {
				if (nums[j] < nums[i] && dp[i] < dp[j] + 1) {   //key
					dp[i] = dp[j] + 1;
				}
			}
		}

		for (int i = 0; i < len; i++) {
			if (dp[i] > ans) {
				ans = dp[i];
			}
		}
		return ans + 1;
    }
}

4.一些总结：