力扣300-最长上升子序列（有点难）

题目：

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

示例:

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

思路：

题目中要我们求长度最长的递增子序列，没要求子序列必须连续。

假设dp(i)表示以第 i 个数字为结尾的最长上升子序列的长度。即在 [0, ..., i] 的范围内，选择以数字 nums[i] 结尾获得的最长上升子序列的长度。关键字一点是以第 i 个数字为结尾，即我们要求 nums[i] 必须被选取。反正一个子序列一定要以一个数字结尾，那我就将状态这么定义，这一点是很重要的。

状态转移方程：遍历第个 i 的数的时候，我们应该 [0, ... ,i - 1] 的dp 都看一遍，如果当前的数 nums[i] 大于之前的某个数，那么 nums[i] 就可以接在这个数后面形成一个更长的dp 。把前面的 i 个数都看了， dp[i] 就是它们的最大值加 1。即比当前数要小的那些里头，找最大的，然后加 1 。

状态转移方程即：dp(i) = max( 1 + dp(j) 0<= j < i , nums[i] > nums[j])

最后不要忘了，应该扫描一遍这个 dp[i] 数组，其中最大的就是我们所求的。

代码：

class Solution {
    public int lengthOfLIS(int[] nums) {
        if(nums.length<2){
            return nums.length;
        }
        int[] dp = new int[nums.length];
        Arrays.fill(dp,1);
        for(int i=1;i<nums.length;i++){
            for(int j=0;j<i;j++){
                if(nums[j]<nums[i]){
                    dp[i]=Math.max(dp[j]+1,dp[i]);
                }
            }
        }
        int max=dp[0];
        for(int i=1;i<dp.length;i++){
            if(max<dp[i]){
                max=dp[i];
            }
        }
        return max;
    }
}

力扣674-最长连续递增序列

题目：

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

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        int min=Integer.MIN_VALUE;
        int cnt=0;
        int ant=0;
        for(int i=0;i<nums.length;i++){
            if(nums[i]>min){
                cnt++;
            }else{
                ant=Math.max(cnt,ant);
                cnt=1;
            }
            min=nums[i];
        }
        return Math.max(cnt,ant);
    }
}