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

方法：动态规划

1、创建一个数组dp，记录下数组arr不同位置为结尾时的最长上升子序列长度，可以得到如下的状态方程：

如果存在arr[j] (j < i)小于该位置arr[i]，通过遍历前序的元素得到：dp[i] = max(dp[i], 1 + dp[j])；

2、遍历完数组arr，数组dp中的最大值即为该数组的最长上升子序列长度。

时间复杂度：o(n²)

空间复杂度：o(n)

class Solution {
  public:
    int LIS(vector<int>& arr) {
        // 特殊情况处理
        if (arr.size() == 0)
            return 0;

        vector<int> dp(arr.size(), 1);
		// 初始化为1，只要有元素长度至少为1
        int max_len = 1;
        for (int i = 1; i < arr.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j])
                    dp[i] = max(dp[i], 1 + dp[j]);
            }
            if (dp[i] > max_len)
                max_len = dp[i];
        }

        return max_len;
    }
};