algorithm
최대 경로 합계 알고리즘

최대 경로 합계 기본 정보

최대 경로 합은 해당 경로의 요소 (노드) 합계가 다른 경로보다 큰 경로를 찾는 알고리즘입니다.

예를 들어 아래 그림과 같이 삼각형을 만듭니다.

        3
      7   4
    2   4   6
  8   5   9   3

위 삼각형에서 최대 합계를 갖는 최대 경로를 찾으십시오. 답은 3 + 7 + 4 + 9 = 23

해결책을 찾으려면 항상 Brute-Force 방법에 대한 아이디어를 얻으십시오. Brute-Force 방법은이 4 행 삼각형에 적합하지만 100 행 또는 100 행 이상의 삼각형에 대해 생각하십시오. 그래서 우리는 Brute-Force 방법을 사용하여이 문제를 해결할 수 없습니다.

동적 프로그래밍 접근법으로 넘어 갑시다.

연산:

삼각형 또는 이진 트리의 각 노드마다 최대 경로가 노드를 통과하는 네 가지 방법이 있습니다.

1. 노드 전용
2. Left Child + Node를 통한 최대 경로
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();
    }
}