Μέγιστη αύξουσα υπακολουθία
Το μήκος της σε , κρατώντας για κάθε μήκος το μικρότερο δυνατό τελευταίο στοιχείο.
Πότε
Η άμεση εφαρμογή είναι σπάνια. Πολύ συχνότερα το πρόβλημα ανάγεται σε LIS: ταξινομείς ζευγάρια κατά τη μία συντεταγμένη και ψάχνεις αύξουσα ακολουθία στην άλλη (φάκελοι μέσα σε φακέλους, πύργοι από κουτιά).
Η ιδέα
Το DP είναι . Για χρειάζεται κάτι καλύτερο.
Κρατάμε : το μικρότερο τελευταίο στοιχείο ανάμεσα σε όλες τις αύξουσες υπακολουθίες μήκους που έχουμε δει. Ο πίνακας είναι γνησίως αύξων. Για κάθε νέο , το πρώτο αντικαθίσταται από το : μια υπακολουθία μήκους που τελειώνει σε κάτι επεκτείνεται με το . Αν δεν υπάρχει τέτοιο , το μεγαλώνει τον πίνακα κατά ένα. Η απάντηση είναι το μήκος του πίνακα.
Παγίδες
- Ο δεν είναι η ίδια η υπακολουθία. Για να την ανακατασκευάσεις, κράτα για κάθε στοιχείο τον δείκτη του προηγούμενού του.
- Γνησίως αύξουσα:
lower_bound. Μη φθίνουσα:upper_bound. Το test σε αυτή τη σελίδα έχει πολλές ίσες τιμές για να πιάνει ακριβώς αυτό.
Κώδικας
Χωρίς main: μπαίνει κάτω από τα #include, το using namespace std και το using ll = long long.
// Length of the longest strictly increasing subsequence. O(n log n).
// tail[k] = the smallest possible last element of an increasing subsequence of length k + 1.
// tail stays sorted, so each element replaces the first tail >= it (lower_bound).
// For non-decreasing subsequences use upper_bound instead.
int lisLength(const vector<ll>& a) {
vector<ll> tail;
for (ll x : a) {
auto it = lower_bound(tail.begin(), tail.end(), x);
if (it == tail.end()) {
tail.push_back(x);
} else {
*it = x;
}
}
return tail.size();
}
Ελέγχθηκε σε 3.000 τυχαίες περιπτώσεις απέναντι σε αργή, προφανώς σωστή λύση, με AddressSanitizer και UndefinedBehaviorSanitizer (g++ (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0, 2026-11-18 23:27 UTC).
Για εξάσκηση στο CSES
Με τη σειρά: το πρώτο είναι η καθαρή εφαρμογή, τα επόμενα θέλουν μια παραλλαγή.
- Increasing Subsequence · Dynamic Programming
Περισσότερα στο USACO Guide
- Longest Increasing Subsequence · usaco.guide/gold/lis
Στα αγγλικά, με επιπλέον προβλήματα ανά επίπεδο.