Блог

 def minOperation(A,N):
    operations = 0
    for i in range(N):
        if sum(A[:i 1])<0:
            A[i] = A[i] 1
            operations  = 1
    return operations
 

Что я делаю не так в этом коде?

В вопросе говорится:

Задан массив A[] из N целых чисел. В каждой операции человек может увеличить i-й элемент на 1 (т. е. Установить A[i] = A[i] 1). Задача состоит в том, чтобы вычислить минимальное количество требуемых операций, чтобы в массиве A[] не было префикса, сумма которого меньше нуля. (т. е. для всех i Это условие должно выполняться A[1] A[2] .. A[i] >= 0).

что я делаю не так в этом коде

Ваш код предполагает, что сумма, которая становится отрицательной, всегда может быть решена простым добавлением единицы к последнему члену, но вам может потребоваться внезапно добавить единицу ко всем посещенным до сих пор терминам. Например:

 A = [1, 1, 1, 1, -9]
 

Ваш код не добавит единицу к первым 4 терминам, а затем изменит только -9 на -8, но этого недостаточно. В этот момент вам действительно следует учитывать, что все предыдущие термины должны получить дополнительное очко, чтобы префиксная сумма стала 2 2 2 2-8, что тогда все еще нормально.

Поэтому идея состоит в том, чтобы отслеживать, сколько из них вы добавили, что в то же время укажет, по какому индексу вы можете добавить следующий-при необходимости. Каждый раз, когда ваш текущий итог становится отрицательным, вы знаете, сколько операций вам потребуется дополнительно. Если они доступны, используйте их, чтобы свести общее количество к нулю.

Код:

 def minOperations(lst):
    operations = 0
    total = 0
    for i, val in enumerate(lst):
        total  = val
        if total < 0:
            # Add the number of operations to make the total 0
            operations  = -total
            total = 0
            # If more operations are needed than available...
            if operations > i   1:
                return -1  # ...it cannot be solved
    return operations

# Example run
lst = [1, 1, -5, 3, 2, -4, -1]
print(minOperations(lst))  # 3
 

ПРИМЕЧАНИЕ: нецелесообразно пересчитывать сумму подмассива на каждой итерации. Просто продолжайте добавлять текущее значение к текущей сумме.

Пройдитесь по массиву и вычислите суммы префиксов.

Если для каждой суммы неравенство

 - PrefixSum[i] <= i
 

верно, тогда результат будет

 max(0, - min(PrefixSum))
 

в противном случае результат None (мы не можем добавить достаточное количество)