algorithm
Maximale padsomalgoritme

Maximale padsom Basisinformatie

Maximum Path Sum is een algoritme om een pad te achterhalen zodat de som van het element (knooppunt) van dat pad groter is dan elk ander pad.

Laten we bijvoorbeeld een we een driehoek hebben, zoals hieronder wordt getoond.

        3
      7   4
    2   4   6
  8   5   9   3

Zoek in bovenstaande driehoek het maximale pad met de maximale som. Antwoord is, 3 + 7 + 4 + 9 = 23

Om de oplossing te vinden, krijgen we zoals altijd een idee van de Brute-Force-methode. De Brute-Force-methode is goed voor deze driehoek met 4 rijen, maar denk aan een driehoek met 100 of meer dan 100 rijen. We kunnen de Brute-Force-methode dus niet gebruiken om dit probleem op te lossen.

Laten we overgaan op een dynamische programmeerbenadering.

Algoritme:

Voor elke knoop in een driehoek of in een binaire boom kunnen er vier manieren zijn waarop het maximale pad door de knoop gaat.

1. Alleen knooppunt
2. Max pad door linker kind + knooppunt
3. Max pad door Right Child + Node
4. Max pad door linker kind + knooppunt + Max pad door rechter kind.

Voorbeeld van maximale path path algoritme:

Extra ruimte: O(n)
Tijd Complexiteit: O(n)

C # Implementatie

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