algorithm
Algorithme de somme de chemin maximale

Informations de base sur la somme de chemin maximale

Maximum Path Sum est un algorithme permettant de trouver un chemin tel que la somme des éléments (nœuds) de ce chemin est supérieure à tout autre chemin.

Par exemple, laissez-nous un triangle tel que montré ci-dessous.

        3
      7   4
    2   4   6
  8   5   9   3

Dans le triangle ci-dessus, trouvez le chemin maximum qui a la somme maximum. La réponse est 3 + 7 + 4 + 9 = 23

Pour trouver la solution, nous avons toujours une idée de la méthode Brute-Force. La méthode Brute-Force est bonne pour ce triangle à 4 rangées, mais pensez à un triangle avec 100 ou plus de 100 lignes. Donc, nous ne pouvons pas utiliser la méthode Brute-Force pour résoudre ce problème.

Passons à l'approche de la programmation dynamique.

Algorithme:

Pour chaque nœud dans un triangle ou dans un arbre binaire, il peut y avoir quatre façons pour que le chemin max traverse le nœud.

1. Node seulement
2. Chemin maximum à travers l'enfant gauche + le nœud
3. Max chemin à travers Right Child + Node
4. Chemin maximum à travers l'enfant gauche + Nœud + Max chemin à travers l'enfant droit.

Exemple d'algorithme de somme de chemin maximale:

Espace auxiliaire: O(n)
Complexité temporelle: O(n)

Implémentation C #

public class Node
{

    public int Value;
    public Node Left, Right;

    public Node(int item)
    {
        Value = item;
        Left = Right = null;
    }
}

class Res
{
    public int Val;
}

public class MaximumPathSum
{
    Node _root;
    int FindMaxUtil(Node node, Res res)
    {
        if (node == null) return 0;
        int l = FindMaxUtil(node.Left, res);
        int r = FindMaxUtil(node.Right, res);
        int maxSingle = Math.Max(Math.Max(l, r) + node.Value, node.Value);
        int maxTop = Math.Max(maxSingle, l + r + node.Value);
        res.Val = Math.Max(res.Val, maxTop);
        return maxSingle;
    }

    int FindMaxSum()
    {
        return FindMaxSum(_root);
    }

    int FindMaxSum(Node node)
    {
        Res res = new Res {Val = Int32.MinValue};
        FindMaxUtil(node, res);
        return res.Val;
    }

    public static int Main()
    {
        MaximumPathSum tree = new MaximumPathSum
        {
            _root = new Node(10)
            {
                Left = new Node(2),
                Right = new Node(10)
            }
        };
        tree._root.Left.Left = new Node(20);
        tree._root.Left.Right = new Node(1);
        tree._root.Right.Right = new Node(-25)
        {
            Left = new Node(3),
            Right = new Node(4)
        };
        return tree.FindMaxSum();
    }
}