algorithm
Maximal sökvägsalgoritm

Grundläggande information om maximal sökväg

Maximal Path Sum är en algoritm för att ta reda på en sökväg så att summan av elementet (nod) för den sökvägen är större än någon annan väg.

Låt oss till exempel ha en vi en triangel som visas nedan.

        3
      7   4
    2   4   6
  8   5   9   3

I triangeln ovan, hitta den maximala vägen som har maximal summa. Svaret är 3 + 7 + 4 + 9 = 23

För att ta reda på lösningen får vi som alltid en uppfattning om Brute-Force-metoden. Brute-Force-metoden är bra för denna fyra rader-triangeln, men tänk på en triangel med 100 eller mer än 100 rader. Så vi kan inte använda Brute-Force-metoden för att lösa detta problem.

Låt oss gå till dynamisk programmeringsmetod.

Algoritm:

För varje nod i en triangel eller i ett binärt träd kan det finnas fyra sätt att maxvägen går igenom noden.

1. Endast nod
2. Maxväg genom vänster barn + nod
3. Maxväg genom Right Child + Node
4. Max sökväg genom vänster barn + nod + max sökväg genom höger barn.

Exempel på maximal sökvägssumalgoritm:

Space Auxiliary: O(n)
Tidskomplexitet: O(n)

C # Implementering

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