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

常规动态规划

#include <iostream>
#include <vector>

using namespace std;

class solution
{
public:
    int getResult(vector<int> &nums)
    {
        int n = nums.size();
        vector<int> dp(n, 1);
        int ret = dp[0];
        
        for (int i = 1; i < n; i++)
        {
            for (int j = 0; j < i; j++)
            {
                if (nums[i] > nums[j])
                {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            ret = max(ret, dp[i]);
        }
        
        return ret;
    }
};

int main()
{
    int n;
    solution mSolution;
    
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++)
    {
        cin >> nums[i];
    }
    cin.get();
    cout << mSolution.getResult(nums) << endl;
    
    return 0;
}

二分+贪心

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class solution
{
public:
        int getResult(vector<int> &nums)
    {
        int n = nums.size();
        vector<int> dp(n);
        dp[0] = nums[0];
        int len = 1;
        
        for (int i = 1; i < n; i++)
        {
            if (nums[i] > dp[len - 1])
            {
                dp[len++] = nums[i];
            }
            else
            {
                int j = lower_bound(dp.begin(), dp.begin() + len, nums[i]) - dp.begin();
                dp[j] = nums[i];
            }
        }
        
        return len;
    }
};

int main()
{
    int n;
    solution mSolution;
    
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++)
    {
        cin >> nums[i];
    }
    cin.get();
    cout << mSolution.getResult(nums) << endl;
    
    return 0;
}

树状数组

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

struct Node
{
    int __val;
    int __idx;
    Node(int val, int idx) : __val(val), __idx(idx) {}
};

class TreeVec
{
public:
    TreeVec(int n)
    {
        __tVec = vector<int>(n, 0);
    }
    
    int lowerbit(int x)
    {
        return x & (-x); // x & (~x + 1)
    }
    
    void modify(int x, int y)
    {
        while (x < __tVec.size())
        {
            __tVec[x] = max(__tVec[x], y);
            x += lowerbit(x);
        }
    }
    
    int query(int x)
    {
        int ret = INT_MIN;
        while (x)
        {
            ret = max(ret, __tVec[x]);
            x -= lowerbit(x);
        }
        
        return ret;
    }

public:
    vector<Node> __nodeVec;
    vector<int> __tVec;
};

class solution
{
public:
    int getResult(vector<int> &nums, int n)
    {
        TreeVec mTreeVec(nums.size());
        
        for (int i = 1; i < n; i++)
        {
            mTreeVec.__nodeVec.emplace_back(Node(nums[i], i));
        }
        sort(mTreeVec.__nodeVec.begin(), mTreeVec.__nodeVec.end(), [](Node a, Node b)
             {
                 return a.__val == b.__val ? a.__idx < b.__idx : a.__val < b.__val;
             });
        
        int ret = INT_MIN;
        for (auto [val, idx] : mTreeVec.__nodeVec)
        {
            int tMax = mTreeVec.query(idx);
            mTreeVec.modify(idx, ++tMax);
            ret = max(ret, tMax);
        }
        
        return ret;
    }
};

int main()
{
    int n;
    solution mSolution;
    
    cin >> n;
    vector<int> nums(n + 1); // 树状数组下标从1开始
    for (int i = 1; i <= n; i++)
    {
        cin >> nums[i];
    }
    cin.get();
    
    int m = unique(nums.begin(), nums.end()) - nums.begin(); // 去重操作，不去重就是最长非下降子序列
    
    cout << mSolution.getResult(nums, m) << endl;
    
    return 0;
}