题解 | #最长上升子序列(一)#
最长上升子序列(一)
https://www.nowcoder.com/practice/5164f38b67f846fb8699e9352695cd2f
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 给定数组的最长严格上升子序列的长度。 * @param arr int整型vector 给定的数组 * @return int整型 */ int LIS(vector<int>& arr) { // write code here int n = arr.size(); if (n < 1) { return 0; } // dp用来保存以i结尾的序列,其最长的上升子序列 std::vector<int> dp(n, 1); int max_len = 1; for (int i = 1; i < arr.size(); i++) { int max_tmp = 1; for (int j = 0; j < i; j++) { if (arr[i] > arr[j]) { max_tmp = max(max_tmp, dp[j] + 1); } } dp[i] = max_tmp; //std::cout << "i: " << i << ", len: " << dp[i] << std::endl; max_len = max(max_len, dp[i]); } return max_len; } };