最长递增子序列

给定一个未排序的整数数组，找到最长递增子序列的个数。

输入: [1,3,5,4,7]
输出: 2
解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。

确定状态

最后一步

dp[i]代表num[i]结尾的这个元素的最长递增子序列

子问题

dp[i]之前的dp[0] ~ dp[i-1]中的取num[i]大于0~i-1的值

转移方程

在num[i]大于之前元素的前提下，求最大值

初始和边界条件

将dp数组初始为1，因为递增子序列至少包含自己

计算顺序

从小到大计算

public class Solution3 {

    public int lengthOfLIS(int[] nums) {

        int[] dp = new int[nums.length];

        Arrays.fill(dp, 1);

        for (int i = 0; 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);
                }

            }
        }

        int res = 0;

        for (int i = 0; i < dp.length; i++) {
            res = Math.max(res, dp[i]);
        }

        return res;


    }
   }