algorithm
अधिकतम पथ योग एल्गोरिथ्म

अधिकतम पथ योग मूल जानकारी

अधिकतम पथ योग एक पथ का पता लगाने के लिए एक एल्गोरिथ्म है जैसे कि उस पथ का तत्व (नोड) किसी भी अन्य पथ से अधिक है।

उदाहरण के लिए, हमारे पास एक त्रिकोण है जैसा कि नीचे दिखाया गया है।

        3
      7   4
    2   4   6
  8   5   9   3

ऊपर त्रिकोण में, अधिकतम पथ खोजें जिसमें अधिकतम योग है। उत्तर है, 3 + 7 + 4 + 9 = 23

समाधान का पता लगाने के लिए, हमेशा की तरह हमें ब्रूट-फोर्स पद्धति का विचार मिलता है। Brute-Force विधि इस 4 पंक्तियों त्रिकोण के लिए अच्छा है, लेकिन 100 या 100 से अधिक पंक्तियों के साथ एक त्रिकोण के बारे में सोचें। इसलिए, हम इस समस्या को हल करने के लिए Brute-Force विधि का उपयोग नहीं कर सकते हैं।

आइए गतिशील प्रोग्रामिंग दृष्टिकोण पर जाएं।

कलन विधि:

त्रिकोण में या बाइनरी ट्री में प्रत्येक नोड के लिए चार तरीके हो सकते हैं जो अधिकतम पथ नोड के माध्यम से जाता है।

1. केवल नोड
2. लेफ्ट चाइल्ड + नोड के माध्यम से अधिकतम पथ
3. राइट चाइल्ड + नोड के माध्यम से अधिकतम पथ
4. दाएं बच्चे के माध्यम से अधिकतम रास्ता बाएं बच्चे + नोड + के माध्यम से अधिकतम पथ।

अधिकतम पथ समरूपता का उदाहरण:

अंतरिक्ष सहायक: O(n)
समय जटिलता: O(n)

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