最长下降子序列c++动态规划

最长下降子序列（Longest Decreasing Subsequence, LDS）是指在一个序列中找到一个最长的子序列，其中每个元素都比前一个元素小。在C++中，我们可以使用动态规划来解决这个问题。下面是一个简单的算法描述：

1. 定义状态：令dp[i]表示以nums[i]结尾的最长下降子序列的长度。

2. 初始化：对于数组的第一个元素，它的LDS长度就是1（dp[0]=1）。

3. 动态规划过程：从第二个元素开始遍历，对于每个nums[i]，检查所有前面的元素nums[j](j < i)：
- 如果nums[j] > nums[i]，说明当前位置可以添加到以nums[j]结尾的下降子序列中，所以更新dp[i] = max(dp[i], dp[j]+1)。

4. 结果存储：遍历结束后，dp数组中的最大值即为整个序列的最大下降子序列长度。

int lengthOfLDS(int* nums, int n) {
    if (n == 0) return 0;
    vector<int> dp(n);
    dp[0] = 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);
            }
        }
    }
    return *max_element(dp.begin(), dp.end());
}