algorithm
Algorytm maksymalnej ścieżki

Informacje podstawowe o maksymalnej ścieżce sumy

Maksymalna suma ścieżek to algorytm znajdujący ścieżkę, dzięki której suma elementu (węzła) tej ścieżki jest większa niż jakakolwiek inna ścieżka.

Na przykład, mamy trójkąt, jak pokazano poniżej.

        3
      7   4
    2   4   6
  8   5   9   3

W powyższym trójkącie znajdź maksymalną ścieżkę o maksymalnej sumie. Odpowiedź brzmi: 3 + 7 + 4 + 9 = 23

Aby znaleźć rozwiązanie, jak zawsze mamy pomysł na metodę Brute-Force. Metoda Brute-Force jest dobra dla tego 4-rzędowego trójkąta, ale pomyśl o trójkącie ze 100 lub więcej niż 100 rzędami. Dlatego nie możemy użyć metody Brute-Force do rozwiązania tego problemu.

Przejdźmy do podejścia do programowania dynamicznego.

Algorytm:

Dla każdego węzła w trójkącie lub w drzewie binarnym mogą istnieć cztery sposoby, przez które maksymalna ścieżka przechodzi przez węzeł.

1. Tylko węzeł
2. Maksymalna ścieżka przez Left Child + Node
3. Maksymalna ścieżka przez Right Child + Node
4. Maksymalna ścieżka przez lewe dziecko + węzeł + Maksymalna ścieżka przez prawe dziecko.

Przykład algorytmu maksymalnej ścieżki sumy:

Space Auxiliary: O(n)
Złożoność czasu: O(n)

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