leetcode674最长连续递增序列_leetcode 674.最长连续递增序列

leetcode674最长连续递增序列

题目要求：
给定一个未经排序的整数数组，找到最长且连续的的递增序列。
时间复杂度：o(n)
空间复杂度：o(1)
例如：1，3，5，4，7
输出：3（1，3，5）
解法：用两个变量，一个保存曾经的最长连续递增序列长度（alreadyMax），一个保存当前最长连续递增序列长度（max）,如果max大于alreadyMax，alreadyMax=max

public int findLengthOfLCIS(int[] nums){
        if(null==nums||nums.length==0)
            return 0;
        int alreadyMax=0;
        int max=1;
        for(int i=1;i<nums.length;i++){
            if(nums[i]>nums[i-1]){
                max++;
            }else{
                if(max>alreadyMax)
                alreadyMax = max;
                max=1;
            }
        }
        return Math.max(max,alreadyMax);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

如果题目要求不连续，而是最大上升子序列，题目就稍难一点，可以划为中等难度
例如：-1, 1, -3, 3
输出：3（-1，1，3）
我们可以先用人类的智慧来模拟，多模拟几遍可能就能找出解法
第一步i=0
1 （-1）
第二步i=1
2 （-1，1）
第三步i=2
-1>-3&&1>-3
2 (-1 , 1)
第四步i=3
3 (-1 , 1 ,3)
第四步i=3时，j=0，由于3>-1,所以dp[3]=dp[0]+1=2
第四步i=3时，j=1，由于3>1,所以dp[3]=dp[1]+1=3（dp[1] = dp[0]+1）
第四步i=3时，j=2，由于3>-3,所以dp[3]=dp[2]+1=2,但是由于2<上一步得到的3，所以不赋值
申请一个动态规划数组dp，初始化为1
当i>j时，如果arr[i]>arr[j]
那么有dp[i] = Math.max(dp[i],dp[j]+1);

	public int maxUpSubArr(int[] arr){
        int[] dp = new int[arr.length];
        for(int i=0;i<arr.length;i++){
            dp[i] = 1;
            for(int j=0;j<i;j++){
                if(arr[i]>arr[j]){
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
            }
        }
        return maxInArr(dp);//遍历数组返回最大的
    }
1
2
3
4
5
6
7
8
9
10
11
12