Longest Ordered Subsequence,POJ,2533

POJ 2533（Longest Ordered Subsequence）是一道经典的动态规划问题，主要考察的是最长上升子序列（Longest Increasing Subsequence，简称LIS）的求解。

题目描述

给定一个长度为N的序列，要求找出这个序列中最长的严格递增子序列的长度。

输入

第一行是一个整数N（1 ≤ N ≤ 1000），表示序列的长度。 第二行包含N个整数，表示序列中的元素。

输出

输出最长严格递增子序列的长度。

示例

输入：

8 1 7 3 5 9 4 8 6

输出：

4

解题思路

1. 定义状态：
   • 设dp[i]表示以第i个元素为结尾的最长上升子序列的长度。
2. 状态转移方程：
   • 对于每一个i（从1到N），我们需要遍历所有j（从1到i-1），如果a[j] < a[i]，则dp[i] = max(dp[i], dp[j] + 1)。
3. 初始状态：
   • 每一个元素自身就是一个长度为1的上升子序列，所以dp[i] = 1。
4. 求解结果：
   • 最终结果是所有dp[i]中的最大值。

代码实现

#include #include #include using namespace std;

for (int i = 1; i <= N; ++i) {
    cin >> a[i];
}

for (int i = 1; i <= N; ++i) {
    for (int j = 1; j < i; ++j) {
        if (a[j] < a[i]) {
            dp[i] = max(dp[i], dp[j] + 1);
        }
    }
}

int ans = 0;
for (int i = 1; i <= N; ++i) {
    ans = max(ans, dp[i]);
}

cout << ans << endl;
return 0;

}

代码解释

1. 输入处理：
   • 首先读取序列长度N，然后读取序列中的元素并存储在a数组中。
2. 动态规划数组初始化：
   • dp数组用于存储以每个元素为结尾的最长上升子序列的长度，初始值为1。
3. 状态转移：
   • 使用两层循环，外层循环遍历每一个元素作为结尾，内层循环遍历所有前面的元素，更新dp[i]的值。
4. 求解结果：
   • 遍历dp数组，找出最大的值即为所求的最长上升子序列的长度。

复杂度分析

• 时间复杂度：O(N^2)，因为有两层嵌套循环。
• 空间复杂度：O(N)，用于存储dp数组和输入序列。

优化

对于更高效的求解，可以使用二分查找优化到O(N log N)的时间复杂度，但上述O(N^2)的解法已经足够应对本题的规模。

希望这个详细的解答能帮助你理解和解决POJ 2533问题。如果有任何进一步的问题，欢迎继续提问！