Kadane Algorithim

Kadane-algorithim

Il s'agit d'une solution JavaScript à l'un des célèbres algorithim de la programmation dynamique de la programmation dynamique de Kadane.

Déclaration de problème

Étant donné un tableau a = {a1, a2,…, un} de n éléments, trouvez la somme maximale possible d'un

Sous-réseau contigu sous-réseau non continu (pas nécessairement contigu) sous-réseau.
Les sous-réseaux / sous-séquences vides ne doivent pas être pris en compte.

Cette vidéo YouTube de Ben Wright pourrait être utile pour comprendre l'algorithme de kadane pour le sous-réseau maximal dans une séquence en 1-D.

Format d'entrée

La première ligne de l'entrée a un cas entier T. T suivant. Chaque cas de test commence par un entier N. Dans la ligne suivante, n entiers suivent représentant les éléments du tableau A.

Contraintes:

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

Le sous-réseau et les sous-séquences que vous considérez devraient avoir au moins un élément.

Format de sortie

Deux espaces séparés, les entiers dénotant le sous-réseau contigu maximum et non contigu. Au moins un entier doit être sélectionné et placé dans les sous-réseaux (cela peut être nécessaire dans les cas où tous les éléments sont négatifs).

Échantillon d'entrée

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

Échantillon de sortie

10 10
10 11

Explication

Dans le premier cas: la somme maximale pour les éléments contiguës et non contiguës est la somme de tous les éléments (comme ils sont tous positifs).

Dans le deuxième cas: [2 -1 2 3 4] -> Cela forme le sous-réseau contigu avec la somme maximale. Pour la somme maximale d'un groupe d'éléments non contraire, ajoutez simplement tous les éléments positifs.