Программирование игр и головоломок

j и располагающийся вправо от этого столбца в строках от i₁ до i₂. Его основание равно inf (l[i₁ : i₂]), а его площадь есть произведение этого основания на его высоту i₂ ? i₁ + 1.

Для столбца j нужно найти максимум этой величины, когда i₁ меняется от 1 до n ? 1 (n — число строк), а i₂ — от i₁ + 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, …) вплоть до первого индекса i₁ , для которого S становится отрицательным. Тогда мы начнем пробегать строку S (i₁ + 1, …), и т. д.

Отсюда следует, что в каждый данный момент нужно знать максимальную подпоследовательность в уже пройденной части; эта подпоследовательность задается номером начала r, номером конца q и своей суммой m. С другой стороны, нужно знать наилучшую заключительную подпоследовательность S (k, i ? 1), предполагая, что вектор пройден вплоть до поля i ? 1. Обозначим через s значение суммы этой заключительной подпоследовательности. Пусть k — номер отроки, дающий этой сумме максимальное значение, а s — сумма всех членов, начиная с k.

Если сумма s положительна, то она и образует максимум на строке с номером k. При переходе к i число a [i] добавляется к s. Если s отрицательно, то новый элемент с номером i и становится оптимальной строчкой, и нужно взять s = а[i].

В этих двух случаях число s нужно сравнить с оптимумом m. Если s оказывается больше, то m нужно заменить на s. Попытаемся составить программу, исходя из того, что мы сейчас обсудим. Нужно уточнить предположение индукции.

Предположим, что вектор пройден от элемента 1 до элемента с номером i ? 1 включительно. Мы знаем лучшую подпоследовательность в этой части: она идет от индекса r до индекса q включительно, и ее сумма равна m: m = S (r, q). С другой стороны, мы внаем наилучшую заключительную подпоследовательность, кончающуюся в i ? 1, т. е. знаем такой индекс k, что сумма S (k, i ? 1) максимальна среди заключительных подпоследовательностей, Значение суммы S (k, i ? 1) равно s. Может случиться, что эта заключительная подпоследовательность является наилучшей возможной во всей пройденной части, и в этом случае имеем r = k, q = i ? 1, s = m. В любом другом случае s ? m. Если i = n ? 1, то весь вектор пройден и получен искомый результат r, q, m.

В противном случае нужно включить элемент a[i]. Если s отрицательно, то a[i] и образует (как единственный участник) наилучший заключительный отрезок; берем k = i, s = a[i]. В противном случае s ? 0 и сумма s + a [i] больше s и больше а [i], и это и есть сумма для наилучшего заключительного отрезка, который по- прежнему начинается с номера k. В этих двух случаях отрезок s становится наилучшим отрезком, если он оказывается больше m.

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

d := 1; f := 1; m := a[1]; s := m; i := 2
ПОКА i ? n ВЫПОЛНЯТЬ
  ЕСЛИ s < 0 ТО k := i; s := a [i]
    ИНАЧЕ s := s + a [i]
  КОНЕЦ_ЕСЛИ
  ЕСЛИ s > m ТО d := k; f := i; m := s
  КОНЕЦ_ЕСЛИ
  i := i + 1
ВЕРНУТЬСЯ

Эта программа осуществляет пробег вектора a один-единственный раз, что и было предписано в условии. Это очень просто, но это совершенно не очевидно.