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

class Solution {
public:
    int LIS(vector<int>& arr) {
        if(arr.empty())
            return 0;
        //设置数组长度大小的动态规划辅助数组
        vector<int> dp(arr.size(), 1); 
        int res = 1;
        for(int i = 1; i < arr.size(); i++){
            for(int j = 0; j < i; j++){
                //可能j不是所需要的最大的，因此需要dp[i] < dp[j] + 1
                if(arr[i] > arr[j] && dp[i] < dp[j] + 1) {
                    //i点比j点大，理论上dp要加1
                    dp[i] = dp[j] + 1; 
                    //找到最大长度
                    res = max(res, dp[i]); 
                }
            }
        }
        return res;
    }
};



// #include <vector>
// class Solution {
// public:
//     /**
//      * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//      *
//      * 给定数组的最长严格上升子序列的长度。
//      * @param arr int整型vector 给定的数组
//      * @return int整型
//      */
//     int ans = 0;
//     void dfs(vector<int>& arr, int index, vector<int>& temp)
//     {
//         int n = arr.size();

//         if(index == n)
//         {
//             int t_n = temp.size();
//             ans = max(ans, t_n);
//             return;
//         }
//         if(temp.empty() || arr[index]>temp.back())
//         {
//             temp.emplace_back(arr[index]);
//             dfs(arr, index+1, temp);
//         }

//         if(!temp.empty())    
//         {
//             temp.pop_back();
//             dfs(arr, index+1, temp);
//         }
//     }

//     int LIS(vector<int>& arr) {
//         // write code here
//         // 深度优先搜索，每个元素有选与不选的可能性

//         vector<int> temp;
//         dfs(arr, 0, temp);
//         return ans;        
//     }
// };