CareerCup

recursive definition should do it in a tree, in a generic graph it would be NP-hard.

int max_path_rec(Node* root, int& max_path)
{
	if (root == nullptr) return numeric_limits<int>::min();	
	int left_branch = max(0, max_path_rec(root->left_, max_path));
	int right_branch = max(0, max_path_rec(root->right_, max_path));
	max_path = max(max_path, root->value_ + left_branch + right_branch);
	return root->value_ + max(left_branch, right_branch);
}

int max_path(Node* root) 
{
	int mpath = numeric_limits<int>::min();
	max_path_rec(root, mpath);
	return mpath;
}

public class FindMaxPathInTree {
	public static class Node {
		public Node left;
		public Node right;
		public int data;
		public Node(int data) {
			super();
			this.data = data;
		}
	}
	public static void main(String[] args) {
		/*Node node = new Node(9);
		node.left = new Node(-2);
		node.right = new Node(7);
		node.left.left = new Node(5);
		node.left.right = new Node(3);
		node.left.left.left = new Node(1);
		node.left.left.right = new Node(4);
		node.left.right = new Node(3);
		node.right.left = new Node(2);
		node.right.right = new Node(9);
		node.right.right.left = new Node(7);
		node.right.right.left.left = new Node(2);
		node.right.right.left.right = new Node(9);
		StringBuilder result = new StringBuilder();*/
		Node node = new Node(-1);
		node.left = new Node(-2);
		node.right = new Node(3);
		node.right.right = new Node(-1);
		StringBuilder result = new StringBuilder();
		findMaxPathInTree(node, new Sum(),result, new StringBuilder());
		System.out.println(result.toString());
	}

	private static class Sum {
		int sum;
	}

	public static int findMaxPathInTree(Node node, Sum sum, StringBuilder maxPath, StringBuilder currPath) {
		int currentSum = 0;
		if (node == null) {
			return 0;
		} else if (node.left == null && node.right == null) {
			if (sum.sum < node.data) {
				sum.sum = node.data;
				maxPath.delete(0, maxPath.length());
				maxPath.append("" + node.data);
			}
			currPath.delete(0, currPath.length());	
			currPath.append("" + node.data);
				currentSum = node.data;
		} else {
			int leftSum = findMaxPathInTree(node.left, sum, maxPath, currPath);
			String leftSumPath = currPath.toString();
			currPath.delete(0, currPath.length());
			int rightSum = findMaxPathInTree(node.right, sum, maxPath, currPath);
			String rightSumPath = currPath.reverse().toString();
			currPath.delete(0, currPath.length());
			// find current sum including left subtree, right subtree, and current node
			if (leftSum + node.data > node.data) {
				int tempSum = node.data + leftSum;
				if (node.data + rightSum > node.data) {
					// append all three for finding tempSum
					tempSum += rightSum;
					if (tempSum > sum.sum) {
						sum.sum = tempSum;
						maxPath.delete(0, maxPath.length());
						maxPath.append("" + leftSumPath + node.data + rightSumPath);
					}
					if (leftSum > rightSum) {
						currPath.append(leftSumPath + node.data);
						currentSum = leftSum + node.data;
					} else {
						currPath.append(rightSumPath + "" + node.data);
						currentSum = rightSum + node.data;
					}
				} else {
					currentSum = leftSum + node.data;
					currPath.append("" + leftSumPath + "" + node.data);
				}
			}
			else if (rightSum + node.data > node.data) {
				int tempSum = node.data + rightSum;
				if (node.data + leftSum > node.data) {
					// append all three for finding tempSum
					tempSum += leftSum;
					if (tempSum > sum.sum) {
						sum.sum = tempSum;
						maxPath.delete(0, maxPath.length());
						maxPath.append("" + leftSumPath + node.data + rightSumPath);
					}
					if (leftSum > rightSum) {
						currPath.append(leftSumPath + node.data);
						currentSum = leftSum + node.data;
					} else {
						currPath.append(rightSumPath + "" + node.data);
						currentSum = rightSum + node.data;
					}
				} else {
					currentSum = rightSum + node.data;
					currPath.append("" + rightSumPath + "" + node.data);
				}
			} else {
				if (node.data > sum.sum) {
					maxPath.delete(0, maxPath.length());
					maxPath.append("" + node.data);
					currPath.append("" + node.data);
					currentSum = node.data;
				}
			}
		}
		return currentSum;

	}
}

#include <iostream>
#include <vector>

using namespace std;

class Node {
	public:
		Node(int val)
		{
			val_ = val;
			left_ = right_ = NULL;
		}
		int val_;
		Node *left_, *right_;
};

class Path {
	public:
		Path()
		{
			sum_ = numeric_limits<int>::min();
		}
		int sum_;
		vector<Node *> path_;
};

Path MaxSumPath(Node *n, Path &out)
{
	if (!n) {
		return Path();
	}
	Path l = MaxSumPath(n->left_, out);
	Path r = MaxSumPath(n->right_, out);
	int sum = n->val_;
	if (l.sum_ > 0) {
		sum += l.sum_;
	}
	if (r.sum_ > 0) {
		sum += r.sum_;
	}
	if (sum > out.sum_) {
		out.sum_ = sum;
		out.path_.clear();
		if (l.sum_ > 0) {
			out.path_.insert(out.path_.end(), l.path_.begin(), l.path_.end());
		}
		out.path_.push_back(n);
		if (r.sum_ > 0) {
			for (int i = r.path_.size() - 1; i >= 0; --i) {
				out.path_.push_back(r.path_[i]);
			}
		}
	}
	Path p = l.sum_ > r.sum_ ? l : r;
	if (p.sum_ < 0) {
		p = Path();
	}
	p.sum_ = (p.sum_ == numeric_limits<int>::min()) ? n->val_ : p.sum_ + n->val_;
	p.path_.push_back(n);
	return p;
}

int main()
{
/*
       (1)
       /
    (2)
    / \
  (3) (4) 
  /   /
(6)	(7)
    / \
  (5) (8)
*/
	Node n1(1);
	Node n2(2);
	Node n3(3);
	Node n4(4);
	Node n5(5);
	Node n6(6);
	Node n7(7);
	Node n8(8);
	n1.left_ = &n2;
	n2.left_ = &n3;
	n2.right_ = &n4;
	n3.left_ = &n6;
	n4.left_ = &n7;
	n7.left_ = &n5;
	n7.right_ = &n8;

	Path path;
	MaxSumPath(&n1, path);
	cout << path.sum_ << ": ";
	for (Node *n : path.path_) {
		cout << n->val_ << "->";
	}
	cout << "\n";
}

My PHP Solution :

<?php
function findLongestPath($root,&$longest){
    
    $valueFromLeft = ($root->left) ? findLongestPath($root->left,$longest) : 0;
    $valueFromRight = ($root->right) ? findLongestPath($root->right,$longest) : 0;
    
    
    $longest =  max($longest,$valueFromLeft + $valueFromRight + $root->value,$valueFromRight + $root->value,$valueFromLeft+ $root->value,$root->value);
    
    return max($valueFromLeft + $root->value , $valueFromRight + $root->value);
    
}


class Tree{
    var $value;
    var $left;
    var $right;
}



$node1 = new Tree();
$node1->value=-10;

$node1->left = new Tree();
$node1->left->value=-1;

$node1->right = new Tree();
$node1->right->value=5;

$node1->left->right = new Tree();
$node1->left->right->value=-2;


$long=0;
findLongestPath($node1,$long);

echo $long;

?>

Some python code, O(n) runtime:

#class Node(object):
#
#    def __init__(self, val):
#        self.val = val
#        self.r = None
#        self.l = None

def biggest(n, curr_sum=0, path=''):
    if n is None:
        return curr_sum, path

    return max(biggest(n.r, curr_sum + n.val, path + "{}-".format(n.val)),
               biggest(n.l, curr_sum + n.val, path + "{}-".format(n.val)),
               key=lambda a: a[0])

def biggest_sum_path(n):
    result = biggest(n)
    print("Path - {}, Sum - {}".format(result[1][:-1], result[0]))

Scala

object MaxPathSum extends App {

  case class Node(weight: Int, left: Option[Node] = None, right: Option[Node] = None) {
    // Return the max path within this tree and the current max path for the path containing this node
    def maxPath: (Int, Int) = {
      val (leftMax, leftPath) = left.map(_.maxPath).getOrElse((0,0))
      val (rightMax, rightPath) = right.map(_.maxPath).getOrElse((0,0))

      val path = List(leftPath + weight, rightPath + weight, weight).max
      val max = List(leftMax, rightMax, path).max
      (max, path)
    }
  }

  val tree =
    Node(-1, Some(Node(2,
        Some(Node(-5)),
        Some(Node(3,
          None,
          Some(Node(6)))))),
      Some(Node(-5,
        Some(Node(1)),
        Some(Node(8))))
  )
  println(tree.maxPath._1)
}