[leetcode] 300. Longest Increasing Subsequence (Medium)

题意：

求最长增长的子序列的长度。

思路：

利用DP存取以i作为最大点的子序列长度。

Runtime: 20 ms, faster than 35.21% of C++ online submissions for Longest Increasing Subsequence.

class Solution

{

public:

  int lengthOfLIS(vector<int> &nums)

  {

    if (nums.size() == )

      return ;

    vector<int> dp(nums.size(), );

    dp[] = ;

    int resNum = ;

    for (int i = ; i < nums.size(); i++)

    {

      int curmaxNum = ;

      for (int j = ; j < i; j++)

      {

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

          curmaxNum = max(dp[j], curmaxNum);

      }

      dp[i] = curmaxNum + ;

      resNum = max(dp[i], resNum);

    }

    return resNum;

  }

};

解法二：

讨论区里的最优解：

利用一个容器去动态存储一个增长子序列，遍历Nums，对每一个nums[i]，在容器中寻找是否有大于等于nums[i]的元素，若存在，则将改值替换为nums[i]；

若不存在，则将nums[i]加入该容器，于是容器中的元素永远是小于关系的。

0ms.

class Solution {

public:

    int lengthOfLIS(vector<int>& nums) {

        vector<int> res;

        for(int i=; i<nums.size(); i++) {

            auto it = std::lower_bound(res.begin(), res.end(), nums[i]);

            if(it==res.end()) res.push_back(nums[i]);

            else *it = nums[i];

        }

        return res.size();

    }

};

巴特西

[leetcode] 300. Longest Increasing Subsequence (Medium)

最新文章

热门文章