kondrackii
@kondrackii
1 + 1 = 11

Как найти оптимальную сумму?

Здравствуйте, помогите мне понять. Есть массив чисел, надо найти два числа, сумма которых не превышает n.
Пример:
arr = [5, 3, 8, 10]
n = 15
логичнее взять 5 и 10

вроде бы ничего сложного, но это получается много if и это вроде как костыль. Как это сделать не костыльно и красиво?
  • Вопрос задан
  • 189 просмотров
Решения вопроса 2
@immelnikoff
Изучаю БД
Методом двух указателей пробегаете весь массив. Как только встретите нужную пару чисел, прерываете цикл.
А если нужна пара с максимальной суммой, не превосходящей n (что скорее всего), то цикл не прерываете.
Ответ написан
Комментировать
LaRN
@LaRN
Senior Developer
1. Сортируем массив по убыванию.
[5, 3, 8, 10] -> [10, 8, 5, 3]
2. Находим первый элемент массива не превышающий n - amin (amin - последний элемент массива, он же минимальный)
Это i = 0 и a[i] = 10 (не превышает 15-3 = 12)
3. Идем от найденного элемента к концу массива (j = i+1...len(a)-1) и берем первый элемент j для
которого выполняется условие a[i] + a[j] <= n.
В вашем случае j = 2 и a[j] = 5.
4. Сохраняемой найденное как промежуточный результат i_cur=i,j_cur=j,sum_cur=a[i] + a[j].
5. Если на предыдущем шаге уже был найден sum_cur, то сравниваем его с текущим и выбираем тот, который больше.
6. Далее, если a[i]+a[i+1]>=sum_cur, то продолжаем с пункта 3 только i=i+1.
7. Если попали сюда, а sum_cur не определён, то решения нет.
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
samodum
@samodum
Какой вопрос - такой и ответ
Много if заменяются циклами
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы