最長遞增子序列c++

以下是使用動態規劃算法解決最長遞增子序列問題的C++代碼：

#include <iostream>
#include <vector>
using namespace std;

int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 1); // dp[i]表示以nums[i]為結尾的最長遞增子序列的長度
    int maxLen = 1;
    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);
            }
        }
        maxLen = max(maxLen, dp[i]);
    }
    return maxLen;
}

int main() {
    vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
    int result = lengthOfLIS(nums);
    cout << "最長遞增子序列的長度為：" << result << endl;
    return 0;
}

該算法的時間複雜度為$O(n^2)$，其中$n$為數組的長度。該算法使用一個一維數組dp來記錄以每個元素為結尾的最長遞增子序列的長度，通過遍歷數組，對於每個元素，找到它之前的最長遞增子序列，並將其長度加一。同時，使用另一個變數maxLen記錄當前所有最長遞增子序列的長度中的最大值。最後返回maxLen即可得到最長遞增子序列的長度。