题解 | #最长上升子序列(一)#

当前值 > 上个值 , dp[当前] = dp[当前-1] + 1,然后当前值向前查找所有比它小的值依次比较Math.max(dp[当前],dp[j] + 1)；

当前值 < 上个值, Math.max(1,dp[i]),向前查找比他小的所有值，找到最大递增长度Math.max(dp[当前],dp[j] + 1)；

public static Integer dp(int b[]){

        int []dp = new int[b.length];

        dp[0] = 1;

        for(int i = 1 ; i < b.length ; i ++){

            for(int j =i-1 ; j >=0;j-- ){

                if(b[i] > b[j] )

                    dp[i] = Math.max(dp[j] + 1,dp[i]);

                else

                    dp[i] = Math.max(1,dp[i]);

            }

        }

        int res = Integer.MIN_VALUE;

        for(int i = 0 ; i < dp.length ; i ++){

            if(res < dp[i])

                res = dp[i];

        }

        return res;

    }