Если x меньше u1, то им следует заменить для построения новой наилучшей последовательности с длиной 1. Если же, наконец, оказывается, что ui < x < ui+1, то x можно присоединить к концу последовательности с длиной i + 1, чтобы получить последовательность с длиной i + 1, которая лучше уже известной, и поэтому ui+1 следует заменить на х. Так как и упорядочена, то вы можете разместить в ней x с помощью дихотомического поиска.
Эта операция требует порядка log2 m действий для m, не превосходящих n. Так как вам требуется n обращений к таблице, то вы получаете верхнюю границу числа действий порядка n log2 n, что чрезмерно завышено.
Головоломка 36.
Предположим, что вы уже прошли первую цепочку вплоть до индекса i − 1 и получили наилучшие слова длины р, меняющейся от 1 до m. Вы рассматриваете символ в положении i и ищете его в другой цепочке. Его первое положение j1 может быть поставлено в конце некоторого слова — скажем, слова длины р1 — и даст слово длины р1 + 1, которое окажется лучшим, чем предыдущее: действительно, если j1 можно поставить после слова длины p1, то это значит, что его значение больше положения последнего символа в наилучшем слове длины р1, но меньше положения последнего символа в слове длины p1 + 1, Рассмотрим теперь второе появление того же символа во второй цепочке: j2 > j1. Его нельзя поставить в конце елова длины p1 + 1, хотя j2 и больше j1, потому что это — другое появление того же символа, и их не нужно смешивать. Поэтому достаточно ограничиться по поводу этого появления символа обращением к таблице в ее части от p1 + 2 до m.
Головоломка 37.
Рассмотрим прямоугольник пробелов, вертикальная граница которого расположена в столбце j и располагающийся вправо от этого столбца в строках от i1 до i2. Его основание равно inf (l[i1 : i2]), а его площадь есть произведение этого основания на его высоту i2 − i1 + 1.
Для столбца j нужно найти максимум этой величины, когда i1 меняется от 1 до n − 1 (n — число строк), а i2 — от i1 + 1 до n.
Когда вы переходите к следующему столбцу, то каждое l уменьшается на 1. В строке, в которой стояла единица, оно становится нулем. Там, где l было равно 0, его нужно вычислить заново. Вы можете попробовать схитрить при вычислении величины inf (l).
В центральном цикле любое введение нового члена может только уменьшить значение минимума.
Головоломка 39.
Рассмотрим значения S для строк i и i' > i. Очевидно
S (i, j) = S (i, i' − 1) + S (i', j).
Если S (i, i' − 1) положительно, то S (i, j) > S (i', j) и строка i остается строкой, которая может содержать максимум.
Но если S (i, i' − 1) < 0, то S (i, j) < S (i', j).
Максимум нужно тогда искать либо среди S (i, j) для j < i', либо среди S (i', j) для j ≥ i'.
Заметим, что S (i', i') = а[i'].
Мы собираемся пробежать строку S (1, …) вплоть до первого индекса i1 , для которого S становится отрицательным. Тогда мы начнем пробегать строку S (i1 + 1, …), и т. д.
Отсюда следует, что в каждый данный момент нужно знать максимальную подпоследовательность в уже пройденной части; эта подпоследовательность задается номером начала r, номером конца q и своей суммой m. С другой стороны, нужно знать наилучшую заключительную подпоследовательность S (k, i − 1), предполагая, что вектор пройден вплоть до поля i − 1. Обозначим через s значение суммы этой заключительной подпоследовательности. Пусть k — номер отроки, дающий этой сумме максимальное значение, а s — сумма всех членов, начиная с k.