P2766 Longest Non-decreasing Subsequence Problem

Given a sequence of positive integers $x_1 \ldots, x_n$. 1. Compute the length $s$ of its longest non-decreasing subsequence. 2. If each element is allowed to be used at most once, compute the maximum number of non-decreasing subsequences of length $s$ that can be extracted from the given sequence. 3. If, in the extracted subsequences, $x_1$ and $x_n$ are allowed to be used multiple times (all other elements are still allowed to be used at most once), compute the maximum number of **different** non-decreasing subsequences of length $s$ that can be extracted from the given sequence. Let $a_1, a_2, \ldots, a_s$ be the indices used to construct $S$, and $b_1, b_2, \ldots, b_s$ be the indices used to construct $T$. For all $i \in [1,s-1]$, we have $a_i \lt a_{i+1}$ and $b_i \lt b_{i+1}$. Then $S$ and $T$ are **different** if and only if there exists $i \in [1,s]$ such that $a_i \neq b_i$.

The first line contains a positive integer $n$, which is the length of the given sequence. The following lines contain $n$ positive integers $x_1, ..., x_n$.

- The first line is the length $s$ of the longest non-decreasing subsequence. - The second line is the maximum number of non-decreasing subsequences of length $s$ that can be extracted. - The third line is the maximum number of **different** non-decreasing subsequences of length $s$ that can be extracted when $x_1$ and $x_n$ are allowed to be used multiple times in the extracted subsequences.

Constraints: $1 \le n \le 500$. Translated by ChatGPT 5