LeetCode/300. 最长上升子序列

300. 最长上升子序列

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例 ：

输入: [10,9,2,5,3,7,101,18]
输出: 4 
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

说明:

• 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
• 你算法的时间复杂度应该为 O(n2) 。

进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

来源：力扣（LeetCode）
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

本题每个当前位置所能获得的最长上升子序列必然和它之前位置的最长子序列有关，所以我们就可以想到用动态规划来解决问题。如何获取当前位置的最长上升子序列？遍历当前元素之前的所有元素，如果当前元素大于之前的某个元素，且当前最长上升子序列长度就是大于位置的索引加一，由此可以写出状态转移方程

$$dp[i]=Math.max(dp[i], dp[j]+1)$$

具体代码如下：

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) return 0;
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        //最少肯定长度为1
        int result = 1;

        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            if (dp[i] > result) {
                result = dp[i];
            }
        }
        return result;
    }
}