领扣LintCode算法问题答案-76. 最长上升子序列

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 {
    /**
     * @param nums: An integer array
     * @return: The length of LIS (longest increasing subsequence)
     */
    public int longestIncreasingSubsequence(int[] nums) {
        // write your code here
        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;
	    }
	}
}

原题链接点这里

鸣谢

非常感谢你愿意花时间阅读本文章，本人水平有限，如果有什么说的不对的地方，请指正。
欢迎各位留言讨论，希望小伙伴们都能每天进步一点点。

最后

以上就是迷路镜子为你收集整理的领扣LintCode算法问题答案-76. 最长上升子序列76. 最长上升子序列题解鸣谢的全部内容，希望文章能够帮你解决领扣LintCode算法问题答案-76. 最长上升子序列76. 最长上升子序列题解鸣谢所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。