Python помогите с задачей
Дан массив целых чисел. Необходимо разбить этот массив на два подмассива так, чтобы разница между суммами чисел в этих подмассивах была минимальной. Не требуется, чтобы размеры подмассивов были равны.
Массив может содержать от 1 до 100 элементов.
Каждый элемент массива может быть любым целым числом от -1000 до 1000.
Реализовать функцию, которая принимает массив целых чисел и возвращает минимально возможную разницу между суммами двух подмассивов.
Нужно достичь оптимального времени выполнения и использования памяти.
Пример:
Входные данные
[1, 2, 3, 4, 5, 6] Выходные данные
1 def min_diff_sum(arr):
total_sum = sum(arr)
n = len(arr)
dp = [0] * (total_sum // 2 + 1)
dp[0] = 1
for num in arr:
for i in range(total_sum // 2, num - 1, -1):
dp[i] = max(dp[i], dp[i - num] + num)
min_diff = float('inf')
for i in range(total_sum // 2 + 1):
if dp[i]:
min_diff = min(min_diff, abs(total_sum - 2 * i))
return min_diff
arr = input("Введите массив целых чисел: ")
arr = list(map(int, arr.split()))
result = min_diff_sum(arr)
print("Минимальная разница между суммами двух подмассивов:", result)
from ast import literal_eval
def min_diff_sub_array(arr):
min_diff, total_sum, prefix_sum = float('inf'), sum(arr), 0
for i in arr:
prefix_sum += i
diff = abs((total_sum - prefix_sum) - prefix_sum)
if (diff < min_diff):
min_diff = diff
return min_diff
print(min_diff_sub_array(literal_eval(input()))) 