Сколько раз я должен l oop, чтобы покрыть все случаи возможных сумм?

Question

Я пытаюсь решить эту проблему конкурентного программирования , используя python3. Задача состоит в том, чтобы, учитывая массив размером n, разбить массив на три последовательных непрерывных части так, чтобы первая часть имела максимальную сумму и равнялась сумме третьей части. Элементы в массиве являются натуральными числами.

Мой подход:

inputN = int(input())   
inputString = input()

usableString = stringToList(inputString)

counting = 0
sum1 = usableString[0]
sum3 = usableString[-1]
maxSum1 = 0
countFromLeft = 1
countFromRight = 2

while counting < inputN-1:
    if sum1 > sum3:
        sum3 += usableString[-countFromRight]
        countFromRight += 1
    elif sum3 > sum1:
        sum1 += usableString[countFromLeft]
        countFromLeft += 1
    elif sum1 == sum3:
        maxSum1 = sum1
        sum1 += usableString[countFromLeft]
        countFromLeft += 1
    counting += 1

print(maxSum1)

1. Мы читаем в массиве элементы и храним их в списке usableString.
2. Мы устанавливаем две переменные sum1 и sum3 для первого и последнего элементов списка соответственно.
3. Мы устанавливаем переменную для отслеживания максимальная сумма первой части списка.
4. Наконец, мы устанавливаем переменную counting равной 0, которая будет представлять количество элементов, добавленных из списка в sum1 или sum3.
5. Остальная часть лога c находится в то время как l oop, который просто проверяет, больше ли sum1, чем sum3 или наоборот, и наоборот, если они равны. После каждой итерации мы добавляем 1 к подсчету, так как дополнительный элемент был включен в деталь. В то время как l oop должен остановиться, когда количество используемых элементов (то есть counting) равно количеству элементов в массиве - 1, так как мы добавили первый и последний элементы перед вводом l oop, что make (array - 2), однако нам все еще нужно l oop еще один раз, чтобы проверить, равны ли sum1 и sum3.

Answer 1

Я проверил ваш представленный алгоритм, и проблема в том, что ваша stringToList функция:

def stringToList(s):
    list=[]
    for elem in s:
        if elem != " ":
            list.append(int(elem))
    return list

Насколько я могу судить, ваш основной алгоритм полностью в порядке, но stringToList делает одну важную вещь неправильно:

>>> stringToList('2 4 6 8 10')
[2, 4, 6, 8, 1, 0]
# should be
[2, 4, 6, 8, 10]

Поскольку каждый символ обрабатывается индивидуально, две цифры 10 превращаются в 1, 0. Более простой способ, который работает правильно, заключается в следующем:

# explanation
>>> input()
'2 4 6 8 10'

>>> input().split(' ')
['2', '4', '6', '8', '10']

>>> map(int, input().split(' ')) # applies the int function to all elements
<map object at 0x...>

>>> list(map(int, input().split(' '))) # converts map object into list
[2, 4, 6, 8, 10]

Извините, что так долго, я закончил делать свой собственный алгоритм для сравнения с вашим, запустил свои собственные тесты, а затем запустил ваш код с помощью метода ввода в список, который я только что объяснил, и понял, что единственная разница заключается в вашей функции stringToList. Это заняло некоторое время, но я надеюсь, что это поможет!

Просто для удовольствия, вот мой алгоритм, и оказалось, что он очень похож на ваш!

array = [1, 3, 2, 1, 4]
n = len(array)
slice = [0, n]
sum = [array[0], 0]
bestSum = 0
while slice[0] < slice[1]-1:
    i = 0 if (sum[0] < sum[1]) else 1
    slice[i] += 1-(2*i)
    sum[i] += array[slice[i]]
    if sum[0] == sum[1]: bestSum = sum[0]
    # print(array[ : slice[0]+1], array[slice[0]+1 : slice[1]], array[slice[1] : ])
print(bestSum)