Задача 14.
Заданы массивы A[1..n] и B[1..n]. Необходимо найти такие индексы i0 и j0, , что
ai0 + bj0 = max (ai + bj ),
где 1<=i<=n, 1<=j<=m , i<j.
|
Решение задачи 14.
Для решения задачи достаточно осуществлять просмотр элементов массивов А и В, фиксируя две величины:
- положение p максимального просмотренного элемента из А;
- значение индексов i0,j0 для максимальной найденной суммы, удовлетворяющей требуемому условию.
Замечание. На начальном этапе p=1, i0=1, j0=2.
При просмотре очередного i элемента из А определяется:
- максимальная сумма из А[i0]+В[j0], А[р]+В[i+1] или А[i]+В[i+1] c пересчетом индексов i0,j0 для максимальной найденной суммы;
- положение p максимального просмотренного элемента из А (сравнивая значения А[р]+А[i]). Процесс выполняется для i от 2 до m-1.
Процесс заканчивается, когда начальный Ni и конечный Ki индексы равны для каждого i.
|
