algorithm
Algoritmo de suma de ruta máxima

Información básica de la suma máxima de ruta

Maximum Path Sum es un algoritmo para encontrar una ruta tal que la suma del elemento (nodo) de esa ruta sea mayor que cualquier otra ruta.

Por ejemplo, tengamos un triángulo, como se muestra a continuación.

        3
      7   4
    2   4   6
  8   5   9   3

En el triángulo anterior, encuentra el camino máximo que tiene la suma máxima. La respuesta es, 3 + 7 + 4 + 9 = 23

Para encontrar la solución, como siempre, tenemos una idea del método de Fuerza Bruta. El método de fuerza bruta es bueno para este triángulo de 4 filas, pero piensa en un triángulo con 100 o más de 100 filas. Por lo tanto, no podemos utilizar el método de fuerza bruta para resolver este problema.

Vayamos al enfoque de la programación dinámica.

Algoritmo:

Para todos y cada uno de los nodos en un triángulo o en un árbol binario, puede haber cuatro formas en que la ruta máxima pasa por el nodo.

1. Solo nodo
2. Ruta máxima a través del hijo izquierdo + nodo
3. Ruta máxima a través del hijo derecho + nodo
4. Ruta máxima a través del hijo izquierdo + Nodo + Ruta máxima a través del niño derecho.

Ejemplo de algoritmo de suma de ruta máxima:

Espacio auxiliar: O(n)
Complejidad del tiempo: O(n)

Implementación de 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();
    }
}