最长上升子序列(LeetCode300. 最长上升子序列)

题目

LeetCode300. 最长上升子序列

解析

与最长连续升序子串不同，这里上升的子序列可以是不连续，这样每一个数组中的元素组成的最长子序列可能依赖于其前面的任一一个小于当前元素的元素。也就是需要记录当前元素之前的元素所组成的最长上升子序列的长度，这样当前元素去查找之前比它小的元素组成新的最长上升子序列，记录下这个值。显然，这是一种动态规划的思想。

我们定义一个一维数组存储对应元素所组成的最长上升子序列的长度，并且遍历时更新记录最长值的变量，当数组全部遍历结束后，返回这个最大值。

动态规划的转移方程为：
假设原数组为nums，记录最长上升子序列的数组为result，默认result数组初始值均为1。
result[i] = max( result[j] + 1, result[i] )，其中0<= j < i且nums[j]<nums[i]

代码

public int lengthOfLIS(int[] nums) {
    if(null == nums || 0 == nums.length){
        return 0;
    }
    //记录最长上升子序列的数组
    int[] result = new int[nums.length];
    //记录最长值的变量
    int maxLength = 1;
    //下标0位置长度为1
    result[0] = 1;
    //遍历数组
    for(int i = 1; i < nums.length; ++i){
        //初始值为1
        result[i] = 1;
        //寻找小于i的下标的元素
        for(int j = i -1; j >= 0; j--){
            //找到下标小于i的且值小于nums[i]的元素
            if(nums[j] < nums[i]){
                //更新新的最长子序列长度 
                result[i] = Math.max(result[j] + 1, result[i]);
            }
        }
        //是当前最长的上升子序列，记录最大值
        if(result[i] > maxLength){
            maxLength = result[i];
        }
    }
    //返回最长值
    return maxLength;
}