300. 最长上升子序列

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

示例:

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

可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n2) 。
进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-increasing-subsequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

暴力：选择所有的子序列进行判断 O((2^n)*n)

LIS(i)表示以第i个数字为结尾的最长上升子序列的长度
LIS(i)表示[0...i]的范围内，选择数字nums[i]可以获得的最长上升子序列的长度

LIS(i)=max(1+LIS(j)) if nums[i]>nums[j]
j<i

image.png

image.png

image.png

    public int lengthOfLIS(int[] nums) {

        if (nums.length < 0) {
            return 0;
        }

        int n = nums.length;

        int[] mems = new int[n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    mems[i] = Math.max(mems[i], mems[j] + 1);
                }
            }
        }

        int ret = 1;

        for (int i = 0; i < n; i++) {
            ret = Math.max(ret, mems[i] + 1);
        }

        return ret;


    }