Найдовша зростаюча підпослідовність

Нам дано масив із $n$ чисел: $a[0 \dots n-1]$. Завдання — знайти найдовшу строго зростаючу підпослідовність у $a$.

Формально ми шукаємо найдовшу послідовність індексів $i_1, \dots i_k$ таку, що

$$i_1 < i_2 < \dots < i_k,\quad a[i_1] < a[i_2] < \dots < a[i_k]$$

У цій статті ми розглянемо кілька алгоритмів розв'язання цього завдання. Також ми обговоримо деякі інші задачі, які можна звести до цієї.

Коли підходить цей алгоритм?

• Чи шукаєте ви найдовшу зростаючу (упорядковану) підпослідовність елементів масиву зі збереженням їхнього порядку, а не суцільний підвідрізок?
• Чи $n$ велике настільки, що квадратичне ДП за $O(n^2)$ надто повільне і потрібен розв'язок за $O(n \log n)$? (якщо $n$ мале — достатньо простого ДП за $O(n^2)$)
• Чи можна звести вашу задачу до LIS (наприклад, найдовша спільна підпослідовність двох перестановок)?

Розв'язок за $O(n^2)$ через динамічне програмування

Динамічне програмування — це дуже загальна техніка, яка дозволяє розв'язувати величезний клас задач. Тут ми застосуємо цю техніку до нашого конкретного завдання.

Спершу ми шукатимемо лише довжину найдовшої зростаючої підпослідовності, а вже потім навчимося відновлювати саму підпослідовність.

Пошук довжини

Щоб виконати це завдання, ми визначимо масив $d[0 \dots n-1]$, де $d[i]$ — це довжина найдовшої зростаючої підпослідовності, яка закінчується елементом з індексом $i$.

інформація

$$\begin{array}{ll} a &= \{8, 3, 4, 6, 5, 2, 0, 7, 9, 1\} \\ d &= \{1, 1, 2, 3, 3, 1, 1, 4, 5, 2\} \end{array}$$

Найдовша зростаюча підпослідовність, яка закінчується на індексі 4, — це $\{3, 4, 5\}$ з довжиною 3; найдовша, що закінчується на індексі 8, — це або $\{3, 4, 5, 7, 9\}$, або $\{3, 4, 6, 7, 9\}$, обидві мають довжину 5; а найдовша, що закінчується на індексі 9, — це $\{0, 1\}$ з довжиною 2.

Ми обчислюватимемо цей масив поступово: спочатку $d[0]$, потім $d[1]$ і так далі. Після того як цей масив обчислено, відповіддю до задачі буде максимальне значення в масиві $d[]$.

Отже, нехай поточний індекс — це $i$. Тобто ми хочемо обчислити значення $d[i]$, а всі попередні значення $d[0], \dots, d[i-1]$ уже відомі. Тоді є два варіанти:

• $d[i] = 1$: шукана підпослідовність складається лише з елемента $a[i]$.

• $d[i] > 1$: підпослідовність закінчуватиметься на $a[i]$, а безпосередньо перед ним буде якесь число $a[j]$ з $j < i$ та $a[j] < a[i]$.

  Легко бачити, що підпослідовність, яка закінчується на $a[j]$, сама буде однією з найдовших зростаючих підпослідовностей, що закінчуються на $a[j]$. Число $a[i]$ просто продовжує цю найдовшу зростаючу підпослідовність ще на одне число.

  Тому ми можемо просто перебрати всі $j < i$ з $a[j] < a[i]$ і взяти найдовшу послідовність, яку отримуємо, дописуючи $a[i]$ до найдовшої зростаючої підпослідовності, що закінчується на $a[j]$. Найдовша зростаюча підпослідовність, що закінчується на $a[j]$, має довжину $d[j]$, і її продовження на одне число дає довжину $d[j] + 1$.

  $$d[i] = \max_{\substack{j < i \\\\ a[j] < a[i]}} \left(d[j] + 1\right)$$

Якщо поєднати ці два випадки, отримуємо остаточну відповідь для $d[i]$:

$$d[i] = \max\left(1, \max_{\substack{j < i \\\\ a[j] < a[i]}} \left(d[j] + 1\right)\right)$$

Реалізація

Ось реалізація описаного вище алгоритму, яка обчислює довжину найдовшої зростаючої підпослідовності.

C++

int lis(vector<int> const& a) {
    int n = a.size();
    vector<int> d(n, 1);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i])
                d[i] = max(d[i], d[j] + 1);
        }
    }

    int ans = d[0];
    for (int i = 1; i < n; i++) {
        ans = max(ans, d[i]);
    }
    return ans;
}

Python

def lis(a: list[int]) -> int:
    n = len(a)
    d = [1] * n  # d[i] — довжина найдовшої зростаючої підпослідовності, що закінчується на i
    for i in range(n):
        for j in range(i):
            if a[j] < a[i]:
                d[i] = max(d[i], d[j] + 1)
    return max(d)

TypeScript

function lis(a: number[]): number {
  const n = a.length;
  const d: number[] = new Array(n).fill(1); // d[i] — довжина LIS, що закінчується на i
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (a[j] < a[i]) d[i] = Math.max(d[i], d[j] + 1);
    }
  }
  return Math.max(...d);
}

Go

func lis(a []int) int {
	n := len(a)
	d := make([]int, n) // d[i] — довжина LIS, що закінчується на i
	for i := range d {
		d[i] = 1
	}
	for i := 0; i < n; i++ {
		for j := 0; j < i; j++ {
			if a[j] < a[i] && d[j]+1 > d[i] {
				d[i] = d[j] + 1
			}
		}
	}
	ans := d[0]
	for i := 1; i < n; i++ {
		if d[i] > ans {
			ans = d[i]
		}
	}
	return ans
}

Відновлення підпослідовності

Поки що ми навчилися лише знаходити довжину підпослідовності, але не саму підпослідовність.

Щоб мати змогу відновити підпослідовність, ми створимо додатковий допоміжний масив $p[0 \dots n-1]$, який обчислюватимемо разом із масивом $d[]$. $p[i]$ буде індексом $j$ передостаннього елемента в найдовшій зростаючій підпослідовності, що закінчується на $i$. Інакше кажучи, індекс $p[i]$ — це той самий індекс $j$, на якому було отримано найбільше значення $d[i]$. Цей допоміжний масив $p[]$ у певному сенсі вказує на предків.

Тоді, щоб отримати підпослідовність, ми просто починаємо з індексу $i$ з максимальним $d[i]$ і йдемо за предками, доки не виведемо всю підпослідовність, тобто доки не досягнемо елемента з $d[i] = 1$.

Реалізація відновлення

Ми трохи змінимо код із попередніх розділів. Ми обчислюватимемо масив $p[]$ разом із $d[]$, а потім обчислимо підпослідовність.

Для зручності спочатку присвоюємо предкам $p[i] = -1$. Для елементів з $d[i] = 1$ значення предка залишиться $-1$, що буде трохи зручнішим для відновлення підпослідовності.

C++

vector<int> lis(vector<int> const& a) {
    int n = a.size();
    vector<int> d(n, 1), p(n, -1);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i] && d[i] < d[j] + 1) {
                d[i] = d[j] + 1;
                p[i] = j;
            }
        }
    }

    int ans = d[0], pos = 0;
    for (int i = 1; i < n; i++) {
        if (d[i] > ans) {
            ans = d[i];
            pos = i;
        }
    }

    vector<int> subseq;
    while (pos != -1) {
        subseq.push_back(a[pos]);
        pos = p[pos];
    }
    reverse(subseq.begin(), subseq.end());
    return subseq;
}

Python

def lis(a: list[int]) -> list[int]:
    n = len(a)
    d = [1] * n
    p = [-1] * n  # p[i] — індекс попереднього елемента в LIS, що закінчується на i
    for i in range(n):
        for j in range(i):
            if a[j] < a[i] and d[i] < d[j] + 1:
                d[i] = d[j] + 1
                p[i] = j

    pos = 0
    for i in range(1, n):
        if d[i] > d[pos]:
            pos = i

    subseq = []
    while pos != -1:
        subseq.append(a[pos])
        pos = p[pos]
    subseq.reverse()
    return subseq

TypeScript

function lis(a: number[]): number[] {
  const n = a.length;
  const d: number[] = new Array(n).fill(1);
  const p: number[] = new Array(n).fill(-1); // p[i] — індекс попередника в LIS
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (a[j] < a[i] && d[i] < d[j] + 1) {
        d[i] = d[j] + 1;
        p[i] = j;
      }
    }
  }

  let pos = 0;
  for (let i = 1; i < n; i++) {
    if (d[i] > d[pos]) pos = i;
  }

  const subseq: number[] = [];
  while (pos !== -1) {
    subseq.push(a[pos]);
    pos = p[pos];
  }
  subseq.reverse();
  return subseq;
}

Go

func lis(a []int) []int {
	n := len(a)
	d := make([]int, n)
	p := make([]int, n) // p[i] — індекс попередника в LIS
	for i := range d {
		d[i] = 1
		p[i] = -1
	}
	for i := 0; i < n; i++ {
		for j := 0; j < i; j++ {
			if a[j] < a[i] && d[i] < d[j]+1 {
				d[i] = d[j] + 1
				p[i] = j
			}
		}
	}

	pos := 0
	for i := 1; i < n; i++ {
		if d[i] > d[pos] {
			pos = i
		}
	}

	var subseq []int
	for pos != -1 {
		subseq = append(subseq, a[pos])
		pos = p[pos]
	}
	for l, r := 0, len(subseq)-1; l < r; l, r = l+1, r-1 {
		subseq[l], subseq[r] = subseq[r], subseq[l]
	}
	return subseq
}

Альтернативний спосіб відновлення підпослідовності

Відновити підпослідовність можна й без допоміжного масиву $p[]$. Ми можемо просто переобчислити поточне значення $d[i]$ і водночас побачити, як було досягнуто максимуму.

Цей спосіб приводить до трохи довшого коду, але натомість ми заощаджуємо трохи пам'яті.

Розв'язок за $O(n \log n)$ через динамічне програмування та бінарний пошук

Щоб отримати швидший розв'язок задачі, ми побудуємо інший розв'язок методом динамічного програмування, який працює за $O(n^2)$, а потім згодом покращимо його до $O(n \log n)$.

Ми використаємо масив динамічного програмування $d[0 \dots n]$. Цього разу $d[l]$ відповідає не елементу $a[i]$ і не префіксу масиву. $d[l]$ буде найменшим елементом, на якому закінчується зростаюча підпослідовність довжини $l$.

Спочатку ми вважаємо, що $d[0] = -\infty$, а для всіх інших довжин $d[l] = \infty$.

Ми знову поступово оброблятимемо числа, спочатку $a[0]$, потім $a[1]$ і т. д., і на кожному кроці підтримуватимемо масив $d[]$ актуальним.

інформація

Для масиву $a = \{8, 3, 4, 6, 5, 2, 0, 7, 9, 1\}$ нижче наведено всі його префікси та відповідні їм масиви динамічного програмування. Зауважте, що значення масиву не завжди змінюються в кінці.

$$\begin{array}{ll} \text{префікс} = \{\} &\quad d = \{-\infty, \infty, \dots\}\\ \text{префікс} = \{8\} &\quad d = \{-\infty, 8, \infty, \dots\}\\ \text{префікс} = \{8, 3\} &\quad d = \{-\infty, 3, \infty, \dots\}\\ \text{префікс} = \{8, 3, 4\} &\quad d = \{-\infty, 3, 4, \infty, \dots\}\\ \text{префікс} = \{8, 3, 4, 6\} &\quad d = \{-\infty, 3, 4, 6, \infty, \dots\}\\ \text{префікс} = \{8, 3, 4, 6, 5\} &\quad d = \{-\infty, 3, 4, 5, \infty, \dots\}\\ \text{префікс} = \{8, 3, 4, 6, 5, 2\} &\quad d = \{-\infty, 2, 4, 5, \infty, \dots \}\\ \text{префікс} = \{8, 3, 4, 6, 5, 2, 0\} &\quad d = \{-\infty, 0, 4, 5, \infty, \dots \}\\ \text{префікс} = \{8, 3, 4, 6, 5, 2, 0, 7\} &\quad d = \{-\infty, 0, 4, 5, 7, \infty, \dots \}\\ \text{префікс} = \{8, 3, 4, 6, 5, 2, 0, 7, 9\} &\quad d = \{-\infty, 0, 4, 5, 7, 9, \infty, \dots \}\\ \text{префікс} = \{8, 3, 4, 6, 5, 2, 0, 7, 9, 1\} &\quad d = \{-\infty, 0, 1, 5, 7, 9, \infty, \dots \}\\ \end{array}$$

Коли ми обробляємо $a[i]$, можна поставити собі запитання. Якими мають бути умови, щоб ми записали поточне число $a[i]$ до масиву $d[0 \dots n]$?

Ми покладаємо $d[l] = a[i]$, якщо існує найдовша зростаюча послідовність довжини $l$, що закінчується на $a[i]$, і немає найдовшої зростаючої послідовності довжини $l$, яка закінчується меншим числом. Подібно до попереднього підходу, якщо ми вилучимо число $a[i]$ з найдовшої зростаючої послідовності довжини $l$, то отримаємо іншу найдовшу зростаючу послідовність довжини $l - 1$. Тож ми хочемо продовжити найдовшу зростаючу послідовність довжини $l - 1$ числом $a[i]$, і очевидно, що найкраще підійде та найдовша зростаюча послідовність довжини $l - 1$, яка закінчується найменшим елементом, інакше кажучи, послідовність довжини $l-1$, що закінчується елементом $d[l-1]$.

Найдовша зростаюча послідовність довжини $l - 1$, яку ми можемо продовжити числом $a[i]$, існує саме тоді, коли $d[l-1] < a[i]$. Тож ми можемо просто перебирати кожну довжину $l$ і перевіряти, чи можемо продовжити найдовшу зростаючу послідовність довжини $l - 1$, перевіряючи цей критерій.

Додатково нам також потрібно перевірити, чи, можливо, ми вже знайшли найдовшу зростаючу послідовність довжини $l$ з меншим числом у кінці. Тож ми оновлюємо лише якщо $a[i] < d[l]$.

Після обробки всіх елементів $a[]$ довжина шуканої підпослідовності — це найбільше $l$ з $d[l] < \infty$.

C++

int lis(vector<int> const& a) {
    int n = a.size();
    const int INF = 1e9;
    vector<int> d(n+1, INF);
    d[0] = -INF;

    for (int i = 0; i < n; i++) {
        for (int l = 1; l <= n; l++) {
            if (d[l-1] < a[i] && a[i] < d[l])
                d[l] = a[i];
        }
    }

    int ans = 0;
    for (int l = 0; l <= n; l++) {
        if (d[l] < INF)
            ans = l;
    }
    return ans;
}

Python

def lis(a: list[int]) -> int:
    n = len(a)
    INF = float("inf")
    d = [INF] * (n + 1)  # d[l] — найменший елемент, на якому закінчується LIS довжини l
    d[0] = -INF

    for i in range(n):
        for l in range(1, n + 1):
            if d[l - 1] < a[i] < d[l]:
                d[l] = a[i]

    ans = 0
    for l in range(n + 1):
        if d[l] < INF:
            ans = l
    return ans

TypeScript

function lis(a: number[]): number {
  const n = a.length;
  const INF = Infinity;
  const d: number[] = new Array(n + 1).fill(INF); // d[l] — найменший хвіст LIS довжини l
  d[0] = -INF;

  for (let i = 0; i < n; i++) {
    for (let l = 1; l <= n; l++) {
      if (d[l - 1] < a[i] && a[i] < d[l]) d[l] = a[i];
    }
  }

  let ans = 0;
  for (let l = 0; l <= n; l++) {
    if (d[l] < INF) ans = l;
  }
  return ans;
}

Go

func lis(a []int) int {
	n := len(a)
	const INF = int(1e9)
	d := make([]int, n+1) // d[l] — найменший елемент, на якому закінчується LIS довжини l
	for l := range d {
		d[l] = INF
	}
	d[0] = -INF

	for i := 0; i < n; i++ {
		for l := 1; l <= n; l++ {
			if d[l-1] < a[i] && a[i] < d[l] {
				d[l] = a[i]
			}
		}
	}

	ans := 0
	for l := 0; l <= n; l++ {
		if d[l] < INF {
			ans = l
		}
	}
	return ans
}

Тепер зробимо два важливі спостереження.

1. Масив $d$ завжди буде відсортованим: $d[l-1] < d[l]$ для всіх $i = 1 \dots n$.

   Це тривіально, адже ви можете просто вилучити останній елемент зі зростаючої підпослідовності довжини $l$ і отримаєте зростаючу підпослідовність довжини $l-1$ з меншим завершальним числом.

2. Елемент $a[i]$ оновить щонайбільше одне значення $d[l]$.

   Це безпосередньо випливає з наведеної вище реалізації. У масиві може бути лише одне місце з $d[l-1] < a[i] < d[l]$.

Отже, ми можемо знайти цей елемент у масиві $d[]$ за допомогою бінарного пошуку за $O(\log n)$. Фактично ми можемо просто шукати в масиві $d[]$ перше число, яке строго більше за $a[i]$, і намагатися оновити цей елемент так само, як у наведеній вище реалізації.

Реалізація

Це дає нам покращену реалізацію за $O(n \log n)$:

C++

int lis(vector<int> const& a) {
    int n = a.size();
    const int INF = 1e9;
    vector<int> d(n+1, INF);
    d[0] = -INF;

    for (int i = 0; i < n; i++) {
        int l = upper_bound(d.begin(), d.end(), a[i]) - d.begin();
        if (d[l-1] < a[i] && a[i] < d[l])
            d[l] = a[i];
    }

    int ans = 0;
    for (int l = 0; l <= n; l++) {
        if (d[l] < INF)
            ans = l;
    }
    return ans;
}

Python

from bisect import bisect_left


def lis(a: list[int]) -> int:
    n = len(a)
    INF = float("inf")
    d = [INF] * (n + 1)
    d[0] = -INF

    for i in range(n):
        # Замість громіздкого масиву d з INF можна тримати лише його «корисний» префікс
        # і шукати в ньому позицію через bisect_left (перший елемент >= a[i]).
        # Для строго зростаючої LIS це еквівалентно upper_bound: якщо a[i] вже є в d,
        # то умова d[l-1] < a[i] < d[l] хибна, тож оновлення не відбувається.
        l = bisect_left(d, a[i])
        if d[l - 1] < a[i] < d[l]:
            d[l] = a[i]

    ans = 0
    for l in range(n + 1):
        if d[l] < INF:
            ans = l
    return ans

TypeScript

// Власний lowerBound: повертає індекс першого елемента >= x (аналог bisect_left / std::lower_bound).
function lowerBound(arr: number[], x: number): number {
  let lo = 0;
  let hi = arr.length;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (arr[mid] < x) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

function lis(a: number[]): number {
  const n = a.length;
  const INF = Infinity;
  const d: number[] = new Array(n + 1).fill(INF);
  d[0] = -INF;

  for (let i = 0; i < n; i++) {
    const l = lowerBound(d, a[i]);
    if (d[l - 1] < a[i] && a[i] < d[l]) d[l] = a[i];
  }

  let ans = 0;
  for (let l = 0; l <= n; l++) {
    if (d[l] < INF) ans = l;
  }
  return ans;
}

Go

import "sort"

func lis(a []int) int {
	n := len(a)
	const INF = int(1e9)
	d := make([]int, n+1)
	for l := range d {
		d[l] = INF
	}
	d[0] = -INF

	for i := 0; i < n; i++ {
		// sort.SearchInts повертає перший індекс l з d[l] >= a[i] (аналог lower_bound).
		l := sort.SearchInts(d, a[i])
		if d[l-1] < a[i] && a[i] < d[l] {
			d[l] = a[i]
		}
	}

	ans := 0
	for l := 0; l <= n; l++ {
		if d[l] < INF {
			ans = l
		}
	}
	return ans
}

Відновлення підпослідовності

За допомогою цього підходу також можливо відновити підпослідовність. Цього разу нам доведеться підтримувати два допоміжні масиви. Один із них повідомляє нам індекс елементів у $d[]$. І знову нам потрібно створити масив «предків» $p[i]$. $p[i]$ буде індексом попереднього елемента для оптимальної підпослідовності, що закінчується на елементі $i$.

Ці два масиви легко підтримувати під час ітерації по масиву $a[]$ паралельно з обчисленнями $d[]$. А наприкінці неважко відновити шукану підпослідовність за допомогою цих масивів.

Розв'язок за $O(n \log n)$ зі структурами даних

Замість наведеного вище способу обчислення найдовшої зростаючої підпослідовності за $O(n \log n)$ ми можемо розв'язати задачу й по-іншому: використовуючи деякі прості структури даних.

Повернімося до першого методу. Згадаймо, що $d[i]$ — це значення $d[j] + 1$ з $j < i$ та $a[j] < a[i]$.

Отже, якщо ми визначимо додатковий масив $t[]$ такий, що

$$t[a[i]] = d[i],$$

то задача обчислення значення $d[i]$ еквівалентна знаходженню максимального значення на префіксі масиву $t[]$:

$$d[i] = \max\left(t[0 \dots a[i] - 1] + 1\right)$$

Задача знаходження максимуму на префіксі масиву (який змінюється) — це стандартна задача, яку можна розв'язати багатьма різними структурами даних. Наприклад, ми можемо використати дерево відрізків або дерево Фенвіка.

Цей метод, очевидно, має деякі недоліки: з точки зору довжини та складності реалізації цей підхід буде гіршим за метод із використанням бінарного пошуку. До того ж, якщо вхідні числа $a[i]$ особливо великі, нам довелося б застосовувати певні прийоми, як-от стиснення чисел (тобто перенумерування їх від $0$ до $n-1$) або використання динамічного дерева відрізків (генерувати лише ті гілки дерева, які важливі). Інакше споживання пам'яті буде надто високим.

З іншого боку, цей метод має й деякі переваги: з ним вам не доведеться думати про якісь хитрі властивості в розв'язку методом динамічного програмування. А ще цей підхід дозволяє нам дуже легко узагальнити задачу (див. нижче).

Пов'язані задачі

Ось кілька задач, які тісно пов'язані із задачею знаходження найдовшої зростаючої підпослідовності.

Найдовша неспадна підпослідовність

Це насправді майже та сама задача. Тільки тепер у підпослідовності дозволено використовувати однакові числа.

Розв'язок, по суті, також майже той самий. Нам лише потрібно змінити знаки нерівностей і трохи модифікувати бінарний пошук.

Кількість найдовших зростаючих підпослідовностей

Ми можемо використати перший розглянутий метод — або версію за $O(n^2)$, або версію зі структурами даних. Нам лише потрібно додатково зберігати, скількома способами можна отримати найдовші зростаючі підпослідовності, що закінчуються значеннями $d[i]$.

Кількість способів утворити найдовші зростаючі підпослідовності, що закінчуються на $a[i]$, — це сума всіх способів для всіх найдовших зростаючих підпослідовностей, що закінчуються на $j$, де $d[j]$ максимальне. Таких $j$ може бути кілька, тож нам потрібно підсумувати їх усі.

За допомогою дерева відрізків цей підхід також можна реалізувати за $O(n \log n)$.

Для цієї задачі неможливо використати підхід із бінарним пошуком.

Найменша кількість незростаючих підпослідовностей, що покривають послідовність

Для заданого масиву з $n$ чисел $a[0 \dots n - 1]$ нам потрібно розфарбувати числа в найменшу кількість кольорів так, щоб кожен колір утворював незростаючу підпослідовність.

Щоб розв'язати це, ми зауважимо, що мінімальна потрібна кількість кольорів дорівнює довжині найдовшої зростаючої підпослідовності.

Доведення: Нам потрібно довести двоїстість цих двох задач.

Позначимо через $x$ довжину найдовшої зростаючої підпослідовності, а через $y$ — найменшу кількість незростаючих підпослідовностей, що утворюють покриття. Нам потрібно довести, що $x = y$.

Зрозуміло, що $y < x$ неможливе, бо якщо в нас є $x$ строго зростаючих елементів, то жодні два з них не можуть належати до однієї й тієї самої незростаючої підпослідовності. Тому маємо $y \ge x$.

Тепер покажемо, що $y > x$ неможливе, від супротивного. Припустимо, що $y > x$. Тоді розглянемо будь-який оптимальний набір із $y$ незростаючих підпослідовностей. Перетворимо цей набір таким чином: поки існують дві такі підпослідовності, що перша починається раніше за другу, і перша послідовність починається з числа, більшого за або рівного першому числу другої, ми відчіпляємо це початкове число й приєднуємо його до початку другої. Після скінченної кількості кроків ми маємо $y$ підпослідовностей, і їхні початкові числа утворюватимуть зростаючу підпослідовність довжини $y$. Оскільки ми припустили, що $y > x$, ми дійшли до суперечності.

Отже, звідси випливає, що $y = x$.

Відновлення послідовностей: Бажане розбиття послідовності на підпослідовності можна виконати жадібно. Тобто йдемо зліва направо і призначаємо поточне число тій підпослідовності, що закінчується мінімальним числом, яке більше за або рівне поточному.

Задачі для практики

• ACMSGURU - "North-East"
• Codeforces - LCIS
• Codeforces - Tourist
• SPOJ - DOSA
• SPOJ - HMLIS
• SPOJ - ONEXLIS
• SPOJ - SUPPER
• Topcoder - AutoMarket
• Topcoder - BridgeArrangement
• Topcoder - IntegerSequence
• UVA - Back To Edit Distance
• UVA - Happy Birthday
• UVA - Tiling Up Blocks

Відеоматеріали