bGZo's Notes

longest-increasing-subsequence

2 min read

Content

Solution

  • 状态转移函数：
  • 则本题的答案方程为： 
    class Solution {
      public:
      int lengthOfLIS(vector<int>& nums) {
        int ans = 0, len = nums.size();
        int *dp = new int[len];
        dp[0] = 1;
        for(int i =0 ; i< len; i++){
          int maxInt = dp[0];
        
          for(int j =0 ; j< i; j++ ){
            if(nums[i] > nums[j])
              maxInt = max(maxInt, dp[j] + 1);
          }
          dp[i] = maxInt;
        }
        return *max_element(dp, dp + len);
      }
    };
        // for (auto i : dp){
        //     cout<< i << ", "
        // }
        // compiler error
    class Solution {
      public:
      int lengthOfLIS(vector<int>& nums) {
        int ans = 0, len = nums.size();
        int *dp = new int[len];
        for(int i =0 ; i< len; i++){
          dp[i] = 1;
          for(int j =0 ; j< i; j++ ){
            if(nums[i] > nums[j])
              dp[i] = max(dp[i], dp[j] + 1);
          }
        }
        return *max_element(dp, dp + len);
      }
    };
    class Solution {
      public:
      int lengthOfLIS(vector<int>& nums) {
        int n = (int)nums.size();
        if (n == 0) {
          return 0;
        }
        vector<int> dp(n, 0);
        for (int i = 0; i < n; ++i) {
          dp[i] = 1;
          for (int j = 0; j < i; ++j) {
            if (nums[j] < nums[i]) {
              dp[i] = max(dp[i], dp[j] + 1);
            }
          }
        }
        return *max_element(dp.begin(), dp.end());
      }
    };
- 时空复杂度： $$O(n^{2})$$

Graph View

Recent Notes