算字典序最大最长上升子序列

算字典序最大最长上升子序列是指在一个序列中找到一个连续的子序列，这个子序列的元素按顺序是递增的，并且按照字符的字典序排列也是最大的。例如，在字符串 "abcwefgh" 中，最长的上升子序列是 "abc" 和 "wefg"，因为它们都是递增的，且 "abc" 字典序大于 "wefg"。

算法通常使用动态规划的方法求解，可以定义两个变量，一个是当前元素到结尾的最大上升子序列长度（记作dp[i]），另一个是从前缀开始到当前位置的最大上升子序列长度（记作pre[i]）。预处理前缀的最大值pre数组，然后遍历原序列，更新dp数组。最后dp数组中的最大值即为所求。

相关问题

输出字典序最大的拓扑排序

根据引用中的内容，可以使用拓扑排序算法来求出字典序最大的拓扑排序。具体步骤如下：

1. 对于有向无环图中的每个节点，计算其入度。
2. 将所有入度为0的节点加入队列中。
3. 从队列中取出一个节点，将其加入拓扑序列中，并将其所有邻接节点的入度减1。
4. 如果邻接节点的入度为0，则将其加入队列中。
5. 重复步骤3和步骤4，直到队列为空。

在实现上，可以使用字典来存储每个节点的入度和邻接节点。具体代码如下：

from collections import deque

def topo_sort(graph):
    in_degree = {node: 0 for node in graph}
    adj_nodes = {node: set() for node in graph}
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] += 1
            adj_nodes[node].add(neighbor)
    
    queue = deque([node for node in in_degree if in_degree[node] == 0])
    topo_order = []
    while queue:
        node = queue.popleft()
        topo_order.append(node)
        for neighbor in adj_nodes[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    return topo_order

假设有向无环图的邻接表存储在一个字典`graph`中，可以使用`topo_sort(graph)`函数来求出字典序最大的拓扑排序。

P1309 最长单调递增子序列

题目描述

给出一个长度为n的序列，请找出最长的不下降子序列。（若有多个答案，请输出其中字典序最小的）。

输入格式

第一行包含整数n。

第二行包含n个整数，表示整个序列。

输出格式

第一行包含整数m，表示最长不下降子序列的长度。

第二行包含m个整数，表示最长不下降子序列。

数据范围

1≤n≤1000，1≤序列中的数≤10000

输入样例：

5
3 1 4 2 5

输出样例：

3
3 4 5

算法

(动态规划) $O(n^2)$

时间复杂度

状态数O(n),状态转移O(n),总时间复杂度O(n^2)

空间复杂度

O(n)

C++ 代码

class Solution {
public:
vector<int> LIS(vector<int>& nums) {
vector<int> dp(nums.size(), 1);
vector<vector<int>> path(nums.size());
dp[0] = 1;
path[0].push_back(nums[0]);
int max_length = 1, max_pos = 0;
for (int i = 1; i < nums.size(); i++) {
int max_dp = 1, max_j = -1;
for (int j = 0; j < i; j++) {
if (nums[j] <= nums[i] && dp[j] + 1 > max_dp) {
max_dp = dp[j] + 1;
max_j = j;
}
}
dp[i] = max_dp;
if (max_j != -1) {
path[i] = path[max_j];
}
path[i].push_back(nums[i]);
if (dp[i] > max_length) {
max_length = dp[i];
max_pos = i;
}
}
return path[max_pos];
}
};