package leecode;

/**
 * 最长递增子序列
 * 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
 *
 * 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列
 *
 *
 * @author Tang
 *  2021/5/26
 */
public class LengthOfLIS {

    /**
     * 动态规划问题
     *
     * 每一个子问题： 加上最新的元素与原来的串相比是否增加长度   Len(n) = max( Len(n-1), Len(n) )
     *
     * 底层边界值 n = 1; len(n) = 1
     *
     * @param nums
     * @return Len
     */
    public int lengthOfLIS(int[] nums){
        if(nums.length == 0){
            return 0;
        }

        int maxLen = 1;

        //备忘录数组，纪录每个nums位置的长串长度 (*这里有个问题，如果当前元素所组成的串小于最大串，则当前元素串长记录为1)
        int[] remark = new int[nums.length];
        remark[0] = 1;

        //大循环 遍历nums每个元素
        //为了确定每个元素对应的最大串长 remark[i]
        for(int i = 1; i < nums.length; i++){
            remark[i] = 1;

            //遍历元素i之前的元素，看看有没有比元素i小的
            //如果没有直接忽略i，因为根本不能凑成串，remark[i] = remark[i-1]
            //如果有,获得下标j    计算比较remark[j]+1(i元素) 与remark[i]的大小，决定remark[i]
            for(int j = 0; j < i; j++){
                if(nums[j] < nums[i] ){
                    int lenJ = remark[j] + 1;
                    remark[i] = Math.max(remark[i], lenJ);
                }

            }

            //最后比较remark[i-1]与remark[i]，决定remark[i]是否更新
            maxLen = Math.max(remark[i], maxLen);
        }
        return maxLen;
    }

    public static void main(String[] args) {
        int[] nums = {4, 10, 4, 3, 8, 9};
        System.out.println(new LengthOfLIS().lengthOfLIS(nums));

    }


}