i, j: max((j - i) * min(length[i], length(j)), 0 <= i < j <= n
Наивное решение - полный перебор всех пар.
Эвристическое решение:
Берём два крайних забора (left = 0 и right = n-1), вычисляем площадь участка (right - left) * min(length[left], length[right]).
Учитывая, что при сдвиге границ к центру расстояние вдоль забора (right - left) уменьшается, для увеличения площади участка необходимо увеличение min(length[left], length[right]). Поэтому берём ту границу left или right, длина забора для которой меньше, и начинаем двигать к центру, пока длина забора не станет больше предыдущей (length[left'] > length[left] или length[right'] > length[right]).
Вычисляем новую площадь. Если она больше предыдущей, запоминаем положения заборов. Повторяем процедуру сдвигания заборов.
Или псевдокодом:
leftMax := left := 0
rightMsx := right := n - 1
sMax := (right - left) * min(length[left], length[right])
while (left < right) {
if (length[left] < length[right]) {
left' := left;
while (length[left] <= length[left'] && left' < right) {
left' := left' + 1
}
left := left'
} else {
right' := left;
while (length[right] <= length[right'] && left < right') {
right' := right' - 1
}
right := right'
}
s := (right - left) * min(length[left], length[right])
if (s > sMax) {
sMax := s
leftMax := left
rightMax := right
}
}
