Это была проблема, которая поставила меня в тупик и не позволила вовремя завершить соревнование по программированию. Предысторию можно найти здесь. Решение публикуется в последующем посте.

Проблема

(Объяснение на простом английском языке см. в следующем разделе.)

Вам дан двумерный массив A из N строк и M столбцов. Существует два массива I и J, элементы которых представляют индексы строк и индексы столбцов A соответственно. Должны быть соблюдены следующие условия:

I и J имеют длину L

I не уменьшается. То есть I[p] ≤ I[p+1] для всех o ≤ p ‹ L-1

J не убывает. То есть J[p] ≤ J[p+1] для всех o ≤ p ‹ L-1

Каждый элемент I[p] представляет индекс строки A, а каждый элемент J[p] представляет индекс столбца A . Другими словами:

Для всех 0 ≤ p ‹ L:

0 ≤ I[p] < N

0 ≤ J[p] < M

Индексы строк и столбцов в I и J используются для формирования подпоследовательности A. По сути, это массив длины L с индексами 0 ≤ p ‹ L, где каждый элемент равен A [I[p]] [J[p] ].

Подпоследовательность увеличивается.

Таким образом, для всех o ≤ p ‹ L-1:

A [I[p]] [J[p]] < A [I[p+1]] [J[p+1]]

Какова длина самой длинной возможной подпоследовательности A?

Мой мыслительный процесс

Что они просят простым английским языком?

Понимание проблемы

Всякий раз, когда я вижу проблему такого рода, я понятия не имею, о чем она просит, поэтому, конечно, первое, что я делаю, — это визуализирую ее.

Итак, давайте нарисуем двумерный массив A с N строками и M столбцами.

А как насчет массивов I и J? А эта беспорядочно выглядящая куча символов, A [I[p]] [J[p]]? Давайте попробуем упростить это, взглянув сначала на I и J.

I и J – это массивы индексов строк и столбцов двумерного массива A. Так что же такое I[p]и J[p]? Это будут p-й индекс строки и p-й индекс столбца.

Предположим, что I[p] равно 3, а J[p] равно 3. Таким образом, A [I[p]] [J[p]] просто относится к элементу в A, в строке 3 и >колонка 3!

Итак, как это связано с тем, что мы делаем? Напомним, что мы пытаемся найти подпоследовательность A. (Проще говоря, мы выбираем набор различных элементов из A.) Подпоследовательность упорядочена, поэтому A [I[p]] [J[p]] — это еще один способ обозначить элемент pth в этой подпоследовательности!

Но очевидно, что мы не можем просто взять кучу случайных элементов и на этом остановиться. Итак, каковы условия?

  1. Подпоследовательность должна быть возрастающей, поэтому каждый член должен быть больше предыдущего.
  2. Индексы строк и индексы столбцов должны быть неубывающими. Ключевое отличие состоит в том, что каждый термин может быть больше или равен предыдущему.

Как описать это более простыми словами? Оказывается, это довольно легко понять, когда вы визуализируете это.

Здесь мы видим, что выбираем элементы из A, и есть очевидная закономерность — мы можем двигаться только слева направо и сверху вниз.

Почему мы не можем идти справа налево или снизу вверх? Потому что это нарушило бы требование неубывания I и J.

Имейте в виду, что элементы в подпоследовательности должны увеличиваться (в порядке возрастания).

Как видите, может быть более одной возможной подпоследовательности, в которой ее элементы возрастают.

Наша задача — найти длину максимально длинной подпоследовательности. (Может быть более одной самой длинной подпоследовательности, но всегда есть только одна возможная длина.)

Решение

Я сохранил решение для последующего поста, так как считаю, что эти посты (особенно технические) пишутся довольно долго! Быть в курсе.