领扣LintCode算法问题答案-76. 最长上升子序列
目录
76. 最长上升子序列描述样例 1：样例 2：
题解鸣谢
76. 最长上升子序列
描述
给定一个整数序列，找到最长上升子序列（LIS），返回LIS的长度。
最长上升子序列的定义：
最长上升子序列问题是在一个无序的给定序列中找到一个尽可能长的由低到高排列的子序列，这种子序列不一定是连续的或者唯一的。
样例 1：
输入: [5,4,1,2,3]
输出: 3
解释:
LIS 是 [1,2,3]
样例 2：
输入: [4,2,4,5,3,7]
输出: 4
解释:
LIS 是 [2,4,5,7]
题解
public class Solution {
public int longestIncreasingSubsequence(int[] nums
) {
Pointer
<Integer> max
= new Pointer<>(0);
longestIncreasingSubsequence(nums
, 0, 0, 0, max
);
return max
.getV();
}
private void longestIncreasingSubsequence(int[] nums
, int length
, int index
, int lasNum
, Pointer
<Integer> max
) {
Integer nextMin
= null
;
for (int i
= index
; i
< nums
.length
; i
++) {
if (nums
[i
] > lasNum
|| index
== 0) {
if (nextMin
== null
) {
nextMin
= nums
[i
];
longestIncreasingSubsequence(nums
, length
+ 1, i
+ 1, nums
[i
], max
);
} else if (nums
[i
] < nextMin
) {
nextMin
= nums
[i
];
longestIncreasingSubsequence(nums
, length
+ 1, i
+ 1, nums
[i
], max
);
}
}
}
if (length
> max
.getV()) {
max
.setV(length
);
}
}
class Pointer<T> {
private T v
;
public Pointer(T v
) {
this.v
= v
;
}
public T
getV() {
return v
;
}
public void setV(T v
) {
this.v
= v
;
}
}
}
原题链接点这里
鸣谢
非常感谢你愿意花时间阅读本文章，本人水平有限，如果有什么说的不对的地方，请指正。 欢迎各位留言讨论，希望小伙伴们都能每天进步一点点。
