Kadane Algorithim

Kadane-Algorithim

Esta é a solução JavaScript para um dos famosos Algorithim de Algo de Programação Dinâmica.

Declaração de problemas

Dada uma matriz a = {a1, a2,…, e} de n elementos, encontre a soma máxima possível de um

Subarray contíguo não contíguo (não necessariamente contíguo) subarray.
Subarraias/subsequências vazias não devem ser consideradas.

Este vídeo do YouTube de Ben Wright pode ser útil para entender o algoritmo Kadane para o subarray máximo em uma sequência 1D.

Formato de entrada

A primeira linha da entrada possui um número inteiro de casos T. T a seguir. Cada caso de teste começa com um número inteiro de N. Na próxima linha, n números inteiros seguem representando os elementos da matriz A.

Restrições:

1≤t≤10
1≤n≤105
−104≤ai≤104

O subarray e as subsequências que você considera devem ter pelo menos um elemento.

Formato de saída

Segundo, o espaço separado, os números inteiros que denotam o subarray máximo contíguo e não contíguo. Pelo menos um número inteiro deve ser selecionado e colocado nos subarrays (isso pode ser necessário nos casos em que todos os elementos são negativos).

Entrada de amostra

2
4
1 2 3 4
6
2 -1 2 3 4 -5

Saída de amostra

10 10
10 11

Explicação

No primeiro caso: a soma máxima para elementos contíguos e não contíguos é a soma de todos os elementos (como todos são positivos).

No segundo caso: [2 -1 2 3 4] -> Isso forma a sub -matriz contígua com a soma máxima. Para a soma máxima de um grupo de elementos não-inter-contíguos, basta adicionar todos os elementos positivos.