Розберемо форму «човна». Вона складається з трьох частин:
корпус — горизонтальна смуга в одному рядку y_1, від стовпця x_1 до x_2 (щонайменше дві клітинки);
рубка — вертикальна смуга в стовпці x_3, що йде від рядка корпусу вгору, де x_1 \le x_3 < x_2;
хвіст — вертикальна смуга в стовпці x_4, що перетинає рядок корпусу і йде і вгору, і вниз, де x_3 < x_4 \le x_2.
Обидві вертикальні частини можуть вироджуватися в одну клітинку самого корпусу (умови y_1 \le y_2 та y_3 \le y_1 \le y_4 нестрогі).
Зафіксуємо рядок корпусу і порахуємо для кожного стовпця дві допоміжні величини:
— найкраща сума суцільної вертикальної смуги строго вище рядка у стовпці ; якщо вона від'ємна, беремо (смугу вигідно залишити порожньою);
— те саме для смуги строго нижче рядка .
Обидві рахуються звичайним Кадане по стовпцях і оновлюються за при переході до наступного рядка, тому весь препроцесинг — .
Тепер ідемо по стовпцях зліва направо і ведемо три стани — скільки частин човна вже «зібрано»:
S_j — найкраща сума самого корпусу, що закінчується в стовпці :
P_j — корпус разом з рубкою, де рубка вже поставлена десь у стовпці \le j:
R_j — корпус, рубка і хвіст, де хвіст стоїть у стовпці \le j:
Зверніть увагу на деталь, яку найлегше проґавити: у формулі для R_j береться саме P_{j-1}, а не P_j. Це і кодує вимогу x_3 < x_4 — хвіст мусить стояти строго правіше за рубку.
Відповідь — максимум R_j по всіх рядках і стовпцях.
Складність — . Значення відхилень можуть бути від'ємними, тому ініціалізуйте відповідь «мінус нескінченністю», а не нулем: човен обов'язково має всі три частини, і порожню фігуру брати не можна. Суми накопичуйте у 64-бітному типі.