Algorithm - Maximum Sum of Path

Assuming we have a set of values (see left).  If you write these values down on a a piece of paper, from the top element you can branch downward into either left or right element each has its value. You can get a set of values with triangular look as shown. 

The question is, going from the value at the top to the bottom by choosing to go down the path of either left or right, what is the maximum sum among all possible paths?

---

The Approach

First choose a data structure (node, each point to left child or right child) to present the set of values, then use recursive to solve the problem.

Thought Process

An intuitive way of solving this is to use node to represent the data structure, and use recursive approach to find the maximum sum among all paths.

A node hold value as its data, has a left Node, and a right Node. An head/top Node can be initialized to represent the whole triangular set of values as seen in the main() below.

The maximum sum among all paths starting from a given node is the max of its value plus either the maximum sum among all paths starting from either its left node or right node.

Code Snippet

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Node{
    public int data;
    public Node left;
    public Node right;

    public Node(int value){
        data = value;
    }

    public static int maxPathSum(Node n){
         if (n == null){  // ending condition
             return 0;
         }  
         return Math.max(n.data + maxPathSum(n.left), n.data + maxPathSum(n.right));
    }
    
    public static void main(String[] args){
      Node head = new Node(5);
      head.left = new Node(3);
      head.right = new Node(7);
      head.left.left = new Node(2);
      head.left.right = new Node(9);
      head.right.right = new Node(15);
      head.left.left.left = new Node(99);
      head.left.left.right = new Node(4);
      head.left.right.right = new Node(2);
      head.right.right.right = new Node(8);
      System.out.print(Node.maxPathSum(head));
    }
}
   

The output of this program is 109.

The Performance

The performance of the above recursive algorithm can be view as proportional to the number of various paths. Speaking of number of paths, should the level of the triangular set of numbers is 1, then the number of different paths is 1. If the level of the triangular set of numbers is 2, then the number of different paths is 2. If the level of the triangular set of numbers is 3, then the number of different paths is 4. In a nut shell, the number of different paths of a particular level doubles the previous level:

1 level   ->  1 path
2 levels ->  2 paths
3 levels ->  4 paths
4 levels ->  8 paths
5 levels -> 16 paths

Therefore, the big O notation of the above recursive algorithm is the number of paths which is 2^n where n is the number of level of the triangular set of values.