Subarray de Soma Máxima com o Algoritmo de Dividir e Conquistar
Dado um array de
n inteiros, encontre um subarray contíguo com a soma máxima dos valores, usando a técnica de dividir e conquistar.Entrada
A primeira linha da entrada contém um inteiro
n - número de elementos no array (1 ≤ n ≤ ).A linha seguinte contém
n inteiros separados por um espaço, que representam os elementos do array .Saída
O programa deve imprimir um único inteiro – a maior soma possível entre todos os subarrays do array fornecido.
Exemplos
Entrada | Saída |
9
-2 1 -3 4 -1 3 1 -4 -2 | 7 |
10
1 -2 3 4 -3 1 7 -10 -20 4 | 12 |
Explicação
- -2 1 -3
4 -1 3 1-4 -2 → A soma do subarray destacado é (4 - 1 + 3 + 1) = 7
- 1 -2
3 4 -3 1 7-10 -20 4 → 3 + 4 -3 + 1 + 7 = 12
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB