algorithm
Maximaler Pfadsummen-Algorithmus

Maximale Pfadsumme Basisinformationen

Maximale Pfadsumme ist ein Algorithmus, um einen Pfad herauszufinden, bei dem die Summe des Elements (Knotens) dieses Pfads größer ist als jeder andere Pfad.

Zum Beispiel haben wir ein Wir ein Dreieck wie unten gezeigt.

        3
      7   4
    2   4   6
  8   5   9   3

Suchen Sie im oberen Dreieck den maximalen Pfad mit der maximalen Summe. Die Antwort lautet: 3 + 7 + 4 + 9 = 23

Um die Lösung herauszufinden, bekommen wir wie immer eine Vorstellung von der Brute-Force-Methode. Die Brute-Force-Methode eignet sich für dieses 4-Reihen-Dreieck, man denke aber an ein Dreieck mit 100 oder mehr als 100 Reihen. Daher können wir keine Brute-Force-Methode verwenden, um dieses Problem zu lösen.

Gehen wir zum dynamischen Programmieransatz über.

Algorithmus:

Für jeden Knoten in einem Dreieck oder in einem Binärbaum kann der max-Pfad auf vier Arten durch den Knoten geführt werden.

1. Nur Knoten
2. Maximaler Pfad durch Left Child + Node
3. Maximaler Pfad durch Right Child + Node
4. Maximaler Pfad durch linkes Kind + Knoten + Maximaler Pfad durch rechtes Kind.

Beispiel für den Maximum Path Sum Algorithmus:

Weltraumhilfsmittel: O(n)
Zeitkomplexität: O(n)

C # -Implementierung

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();
    }
}