Pular para o conteúdo

Menor início para um percurso positivo

Fácil#running-sum#prefix-minimum~10 min

A missão

Problema

Você escolhe um número inteiro positivo como valor inicial e depois soma a ele os números de uma lista, um de cada vez, da esquerda para a direita. Retorne o menor valor inicial para o qual a soma acumulada nunca fica abaixo de 1 em nenhum passo.

Exemplos

Input:  nums = [-3, 2, -3, 4, 2]
Output: 5
Por quê: 5 passa por 2, 4, 1, 5, 7, enquanto 4 chegaria a 0 depois do terceiro passo
Input:  nums = [1, 2]
Output: 1
Por quê: o total só cresce, então o menor início positivo funciona
Input:  nums = [1, -2, -3]
Output: 5
Por quê: edge case: o ponto mais baixo vem bem no final

Dicas

0 / 3

Tempo-alvo
O(n)
Espaço-alvo
O(1)

Travou na ideia, e não no código? Gas Station explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado