gistfile1.java

	static class Node
	{
		int val;
		Node left;
		Node right;

		Node(int val, Node left, Node right)
		{
			this.val = val;
			this.left = left;
			this.right = right;
		}
	}

	private static int maxSubseq(Node current, int runningSum)
	{
		if (current == null)
			return runningSum;

		int max = runningSum;
		int leftMax = maxSubseq(current.left, Math.max(runningSum, 0) + current.val);
		max = Math.max(max, leftMax);
		int rightMax = maxSubseq(current.right, Math.max(runningSum, 0) + current.val);
		max = Math.max(max, rightMax);
		
		return max;
	}

	public static int maxSubseq(Node root)
	{
		if (root == null)
			return 0;

		return maxSubseq(root, Integer.MIN_VALUE);
	}