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

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 给定数组的最长严格上升子序列的长度。
     * @param arr int整型vector 给定的数组
     * @return int整型
     */
     int max(int a,int b)
     {
        return a>b?a:b;
     }
    int LIS(vector<int>& arr) {
        // write code here
        if(arr.size()==0) 
            return 0;
        vector<int>dp(arr.size(),1);
        int max = 0;
        for(int i = 1;i < arr.size(); i++)
        {
            for(int j = 0;j < i; j++)
            {
                if(arr[i]>arr[j])
                {
                    dp[i] = Solution::max(dp[i],dp[j]+1);//这里也可以改成将"Solution::"替换成"this->"
                }
            }
        }
        int max_i=dp[0];
        for(int i =0;i<arr.size();i++)
        if(dp[i]>max_i)
        max_i=dp[i];
        return max_i;      
        
    }
};