用c++代码实现动态规划最长递增子序列

在C++中，动态规划是一种解决最优化问题的有效方法，可以用于寻找数组中最长递增子序列（Longest Increasing Subsequence, LIS）。下面是一个简单的C++代码实现，使用了Kadane's Algorithm：

#include <iostream>
#include <vector>

int longestIncreasingSubsequence(std::vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;

    std::vector<int> dp(n, 1); // 初始化每个元素都是单个数就是一个长度为1的递增子序列
    for (size_t i = 1; i < n; ++i) {
        for (size_t j = 0; j < i; ++j) {
            if (nums[i] > nums[j]) {
                dp[i] = std::max(dp[i], dp[j] + 1);
            }
        }
    }

    return *std::max_element(dp.begin(), dp.end()); // 返回最长递增子序列的长度
}

int main() {
    std::vector<int> numbers = {10, 9, 2, 5, 3, 7, 101, 18};
    int result = longestIncreasingSubsequence(numbers);
    std::cout << "Length of the Longest Increasing Subsequence: " << result << std::endl;
    return 0;
}

在这个代码中，`dp[i]` 表示以第 `i` 个元素结尾的最大递增子序列长度。通过遍历整个序列，对于每个元素，我们检查它前面的所有元素，如果当前元素大于前一个元素，则更新该位置的`dp`值。