Дана последовательность целых чисел. Необходимо выбрать из последовательности три числа так, чтобы они образовали убывающую последовательность. Определите максимально возможную сумму выбранных чисел.
Первая строка входного файла содержит число N — общее количество чисел в последовательности. Каждая из следующих N строк содержит одно число, не превышающее 108.
Пример.
Дан входной файл:
4
5
3
6
2
Из этого файла надо выбрать числа 5, 3 и 2, сумма которых равна 10. Выбрать числа 5, 3 и 6 нельзя, так как они не образуют убывающую последовательность.
Вам даны два входных файла (A и B), каждый из которых имеет описанную выше структуру. В ответе укажите два числа: сначала требуемую сумму для файла A, затем — для файла B.
Ответ:
Решение. Приведем решение на языке Python для файла A.
f = open ('27-A.txt')
n = int(f.readline())
a = []
for x in range(n):
a.append(int(f.readline()))
maxi_summa = 0
for i in range (len(a)):
for j in range(i+1,len(a)):
for k in range(j+1,len(a)):
if a[i] > a[j] > a[k]:
maxi_summa=max(maxi_summa, a[i]+a[j]+a[k])
print(maxi_summa)
Приведем решение на языке Python для файлов А и B.
f = open ('27-B.txt')
n = int(f.readline())
a = []
for x in range(n):
a.append([int(f.readline()),x]) # Добавляем в массив число и его индекс
a.sort()
a = a[n-10:] # Так как массив отсортирован по возрастанию, берем последние 10 значений и ищем среди них 3 числа удовлетворяющие условию. Если среди 10 чисел не будет найден ответ, диапазон можно увеличить
a.sort(key=lambda x: x[1]) #сортируем массив по индексам