300. 最长上升子序列

300. 最长上升子序列

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

示例:

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

package com.wangyg.leetcode;

public class Leetcode300 {
    public static void main(String[] args) {
        Solution s = new Solution();
        //输出
        System.out.println(s.lengthOfLIS(new int[]{10, 9, 2, 5, 3, 7, 101, 18}));
    }

    /**
     * 给定一个无序的整数数组，找到其中最长上升子序列的长度。
     * <p>
     * 示例:
     * <p>
     * 输入: [10,9,2,5,3,7,101,18]
     * 输出: 4
     * 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
     * 说明:
     * <p>
     * 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
     * 你算法的时间复杂度应该为 O(n2) 。
     * 进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
     * <p>
     * 维持顺序不变，
     * 最暴力的做法： 从10 开始，然后进行 双层for循环进行遍历，然后重复进行查找，只要符合条件即可， 每个数字都向后找一遍，
     * 然后看最长的子序列， 但是这样会有大量的重复计算，对于每个数字来说，后面的数字都要进行重复的遍历，所以是浪费性能
     * <p>
     * 改进方法： 从末尾进行查找
     * 18： 1
     * 101 : 1
     * 7 :  2 (1->101 / 7-> 18都是2)
     * 3： 3
     * 5： 3
     * 2： 4(2_> 5 / 2->3)
     * 9: 2
     * 10: 2
     * <p>
     * 最终结果： 所有中做大的是  4 ，所以最大的list 是4
     */

    static class Solution {
        /**
         * 方式一： O(n2) 时间复杂度
         *
         * @param nums
         * @return
         */
        public int lengthOfLIS(int[] nums) {
            //获取长度
            int len = nums.length;
            //0 1情况
            if (len < 2) return len;
            int[] record = new int[len + 1];
            record[len - 1] = 1; //最后一个位置
            int ans = -1;
            for(int i = len-2; i>= 0; i--){ //从倒数第二个元素位置开始，进行倒叙计算
                int cur = nums[i];//获取当前值
                int max = 0;
                //内循环，向后进行遍历
                for (int j = i + 1; j < len; j++) {
                    //判断如果cur 比 后面值小  &&  max < record[j]
                    if (cur < nums[j] && max < record[j]) {
                        max = record[j]; // 获取最大的max
                    }
                }
                //当前位置的record[i] = max +1
                record[i] = max+1;
                //比较获取最大值 ，赋值给ans
                if(record[i] > ans) ans = record[i];
            }
            return ans;
        }
    }
}