Эта задача - от вступительного испытания до курса по кибербезопасности с закрытым числом. Во всяком случае, это не имеет отношения к кибербезопасности, это просто для проверки учащихся логических навыков и навыков кодирования.
задача
Напишите программу, которая удаляет записи из массива так, чтобы оставшиеся значения сортировались в строго убывающем порядке, а их сумма была максимизирована среди всех других возможных убывающих последовательностей.
Вход и выход
Входной будет массив целочисленных значений строго больше , чем 0
и все отличаются друг от друга . Вы можете выбрать, читать ли входные данные из файла, командной строки или стандартного ввода.
Выход будет отсортированным по убыванию подмассивом входного массива, сумма которого больше, чем у любого другого возможного отсортированного по убыванию подмассива.
Примечание: [5, 4, 3, 2]
является подмассивом [5, 4, 1, 3, 2]
, даже если 4
и 3
не являются смежными. Просто потому, что 1
лопнуло.
Брутфорс решение
Самым простым решением, конечно, будет итерация среди всех возможных комбинаций данного массива и поиск отсортированного с наибольшей суммой, которая была бы в Python :
import itertools
def best_sum_desc_subarray(ary):
best_sum_so_far = 0
best_subarray_so_far = []
for k in range(1, len(ary)):
for comb in itertools.combinations(ary, k):
if sum(comb) > best_sum_so_far and all(comb[j] > comb[j+1] for j in range(len(comb)-1)):
best_subarray_so_far = list(comb)
best_sum_so_far = sum(comb)
return best_subarray_so_far
К сожалению, поскольку проверка того, отсортирован ли массив, и вычисление суммы его элементов, и так как эта операция будет выполняться раз для от до , асимптотическая сложность времени будет
Вызов
Ваша цель состоит в том, чтобы добиться лучшей сложности во времени, чем описанная выше грубая сила. Решение с наименьшей асимптотической сложностью по времени является победителем задачи. Если два решения имеют одинаковую асимптотическую сложность по времени, победителем будет решение с наименьшей асимптотической пространственной сложностью.
Примечание: вы можете рассмотреть чтение, запись и сравнение атомарных даже в больших количествах.
Примечание. Если имеется два или более решений, верните одно из них.
Контрольные примеры
Input: [200, 100, 400]
Output: [400]
Input: [4, 3, 2, 1, 5]
Output: [4, 3, 2, 1]
Input: [50, 40, 30, 20, 10]
Output: [50, 40, 30, 20, 10]
Input: [389, 207, 155, 300, 299, 170, 158, 65]
Output: [389, 300, 299, 170, 158, 65]
Input: [19, 20, 2, 18, 13, 14, 8, 9, 4, 6, 16, 1, 15, 12, 3, 7, 17, 5, 10, 11]
Output: [20, 18, 16, 15, 12, 7, 5]
Input: [14, 12, 24, 21, 6, 10, 19, 1, 5, 8, 17, 7, 9, 15, 23, 20, 25, 11, 13, 4, 3, 22, 18, 2, 16]
Output: [24, 21, 19, 17, 15, 13, 4, 3, 2]
Input: [25, 15, 3, 6, 24, 30, 23, 7, 1, 10, 16, 29, 12, 13, 22, 8, 17, 14, 20, 11, 9, 18, 28, 21, 26, 27, 4, 2, 19, 5]
Output: [25, 24, 23, 22, 17, 14, 11, 9, 4, 2]
Ответы:
Perl
Это должно быть O (n ^ 2) во времени и O (n) в пространстве
Дать числа, разделенные пробелом в одной строке, в STDIN
источник
Как это устроено
bestSubarrays xs
является последовательностью подмассивов,xs
которые находятся на эффективной границе {наибольшая сумма, наименьший первый элемент}, упорядоченные слева направо путем увеличения суммы и увеличения первого элемента.Чтобы перейти от
bestSubarrays xs
кbestSubarrays (x:xs)
, мыx
, и правую сторону с первыми элементами больше, чемx
,x
к крайнему правому подмассиву слева,источник
Этот ответ расширяет ответ Тон Хоспель.
Проблема может быть решена с помощью динамического программирования с использованием рекурсии
Попробуйте онлайн!
источник