LintCode 76. Longest Increasing Subsequence 原创Java参考解答
问题描述
http://www.lintcode.com/en/problem/longest-increasing-subsequence/
Given a sequence of integers, find the longest increasing subsequence (LIS).
You code should return the length of the LIS.
Clarification
What’s the definition of longest increasing subsequence?
- The longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence’s elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique.
- https://en.wikipedia.org/wiki/Longest_increasing_subsequence
Example
For [5, 4, 1, 2, 3], the LIS is [1, 2, 3], return 3
For [4, 2, 4, 5, 3, 7], the LIS is [2, 4, 5, 7], return 4
解题思路
- 找极值的问题，不难判断旨在题目考察动态规划。
- 定义本题的动态规划状态转移方程f[i]：到第i位置时发现的最长LIS长度。
- 状态初始化，每一个f[i]为1。
- 通过一个二重循环，依次计算i前面所有位置到第i位置的LIS长度。
- 最后循环整个数组，看哪一个位置有最长LIS长度。
参考代码
public class Solution {
/**
* @param nums: The integer array
* @return: The length of LIS (longest increasing subsequence)
*/
public int longestIncreasingSubsequence(int[] nums) {
// write your code here
if (nums == null || nums.length == 0) {
return 0;
}
// the longest subsequence length to the index(x) position
int[] f = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
f[i] = 1;
}
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
f[i] = Math.max(f[i], f[j] + 1);
}
}
}
int max = 0;
for (int i = 0; i < nums.length; i++) {
max = Math.max(f[i], max);
}
return max;
}
}