?LeetCode刷題實(shí)戰(zhàn)300：最長(zhǎng)遞增子序列

示例 1：

輸入：nums = [10,9,2,5,3,7,101,18]
輸出：4
解釋：最長(zhǎng)遞增子序列是 [2,3,7,101]，因此長(zhǎng)度為 4 。

示例 2：

輸入：nums = [0,1,0,3,2,3]
輸出：4

示例 3：

輸入：nums = [7,7,7,7,7,7,7]
輸出：1

#pragma once
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
#define NAMESPACE_LENGTHOFLIS namespace NAME_LENGTHOFLIS {
#define NAMESPACE_LENGTHOFLISEND }
NAMESPACE_LENGTHOFLIS
 
// 動(dòng)態(tài)規(guī)劃
// 遞推公式：dp[i]=max(dp[j])+1,其中0≤j<i且num[j]<num[i]
// 時(shí)間復(fù)雜度：O(n^2), 空間復(fù)雜度：O(n)
class Solution1 
{
public:
    int lengthOfLIS(vector<int>& nums) 
    {
        int n=(int)nums.size();
        if (n == 0) return 0;
        vector<int> dp(n, 0);
        int maxLen = 1;
        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);
                    maxLen = max(maxLen, dp[i]);
                }
            }
        }
        
        //return *max_element(dp.begin(), dp.end());
        return maxLen;
    }
};
 
// 動(dòng)態(tài)規(guī)劃
// dp[i] = max(dp[j]) + 1, 其中 0 ≤ j < i 且 num[j] < num[i] 
class Solution
{
public:
  // 返回不小于目標(biāo)值的位置 
    int search(vector<int> & nums, int target)
    {
        int l = 0;
        int r = nums.size() - 1;
        while(l < r)
        {
            int mid = (r + l) / 2;
            if(target == nums[mid])
               return mid;
            else if(target > nums[mid])
               l = mid + 1;
            else if(target < nums[mid])
               r = mid;
        }
        return l;
    }
 
    int lengthOfLIS(vector<int>& nums) 
    {
        int len = nums.size();
        vector<int> dp;
        if(len <= 0) return 0;
        dp.push_back(nums[0]);
        for(int i = 1;i < len;i++)
        {
            if(nums[i] > dp[dp.size() - 1])
                dp.push_back(nums[i]);
            else
            {
                 //auto it = lower_bound(dp.begin(), dp.end(), nums[i]);
                //*it = nums[i];
 
                int p = search(dp,nums[i]);
                dp[p] = nums[i];
            }
        }
 
         return dp.size();
    }
};
 
以下為測(cè)試代碼//
// 測(cè)試 用例 START
void test(const char* testName, vector<int>& nums, int expect)
{
    Solution_1 s1;
    int result1 = s1.lengthOfLIS(nums);
    Solution_2 s2;
    int result2 = s2.lengthOfLIS(nums);
    if (expect == result1 && expect == result2)
        cout << testName << ", solution passed." << endl;
    else
        cout << testName << ", solution failed. expect:" << expect << ", result1:" <<result1 << ", result2:" << result2 << endl;
}
 
// 測(cè)試用例
void Test1()
{
    vector<int> nums = { 10,9,2,5,3,7,101,18 };
    int expect = 4;
    
    test("Test1()", nums, expect);
}
 
void Test2()
{
    vector<int> nums = { 10,11,1,2,3,12,13,4 };
    int expect = 5;
 
    test("Test2()", nums, expect);
}
 
NAMESPACE_LENGTHOFLISEND
// 測(cè)試 用例 END
//
 
void LengthOfLIS_Test()
{
    NAME_LENGTHOFLIS::Test1();
    NAME_LENGTHOFLIS::Test2();
}