最长上升子序列

题意

给定一个整数序列,找到最长上升子序列(LIS),返回LIS的长度。

最长上升子序列问题是在一个无序的给定序列中找到一个尽可能长的由低到高排列的子序列,这种子序列不一定是连续的或者唯一的。

样例

给出 [5,4,1,2,3],LIS 是 [1,2,3],返回 3
给出 [4,2,4,5,3,7],LIS 是 [2,4,5,7],返回 4

思路

1, 3, 5, 2, 8, 4, 6,对于 6 来说,它的 LIS 是它的前一个数,也就是 4 小于它(4 < 6)的情况下,将 4 的(LIS + 1)就是 6 个 LIS,以此类推。

代码实现

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
26
public class Solution {
/**
* @param nums: The integer array
* @return: The length of LIS (longest increasing subsequence)
*/
public int longestIncreasingSubsequence(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}

int[] lis = new int[nums.length];
int max = 0;
for (int i = 0; i < nums.length; i++) {
int tempMax = 0;
for (int j = 0; j < i; j++) {
if (lis[j] > tempMax && nums[j] < nums[i])
tempMax = lis[j];
}

lis[i] = tempMax + 1;

max = lis[i] > max ? lis[i] : max;
}
return max;
}
}

原题地址

LintCode:最长上升子序列

坚持原创技术分享,您的支持将鼓励我继续创作!