CareerCup

More compact version without recursion. Bottom up strategy:

public class TriangleMaxSum {
	
	private Integer[][] maxSum;
	
	public int maxSum(int[][] triangle) {
		maxSum = new Integer[triangle.length][];
		for (int r=triangle.length-1;r>=0;--r) {
			maxSum[r] = new Integer[triangle[r].length];
			for (int c=0; (c < triangle[r].length); ++c) {
				maxSum[r][c] = triangle[r][c];
				if (r != (triangle.length-1)) {
					maxSum[r][c] += Math.max(maxSum[r+1][c], maxSum[r+1][c+1]);
				}
			}
		}
		return maxSum[0][0];
	}

}

1) use the standard A.P. formula- n(n+1)/2
2) This is the standard Google tree vertical sum problem.Logic is root->data + root->(left->right->data) until left->right is null. This sum would be the first level sum for the root node.

Solving using DP (Same solution as coderanjiy666, but with caching):
Space and Time will be O(n), since each element path is calculated just once.

public class TriangleMaxSum {
	
	private int[][] triangle;
	private Integer[][] maxSum;
	
	public TriangleMaxSum(int[][] triangle) {
		this.triangle = triangle;
		maxSum = new Integer[triangle.length][];
		for (int i=0; i<maxSum.length; ++i) {
			maxSum[i] = new Integer[triangle[i].length];
		}
	}
	
	public int maxSum() {
		return maxSum(0,0);
	}
	
	private int maxSum(int r, int c) {
		if (r >= maxSum.length)
			return 0;
		
		if (maxSum[r][c] != null)
			return maxSum[r][c];
		
		maxSum[r][c] = triangle[r][c] + Math.max(maxSum(r+1, c), maxSum(r+1, c+1));
		return maxSum[r][c];
	}

}

public class TriangleMaxSumTest {

	private int[][] createRandomTriangle(int rows) {
		Random rand = new Random();
		int[][] triangle = new int[rows][];
		for (int cols = 1, r=0; r<rows; ++r, ++cols) {
			triangle[r] = new int[cols];
			for (int c = 0; c<cols; ++c) {
				triangle[r][c] = rand.nextInt(100);
			}
		}
		return triangle;
	}
	
	@Test
	public void testMaxSum() {
		int[][] triangle1 = createRandomTriangle(1000);
		TriangleMaxSum maxSum = new TriangleMaxSum(triangle1);
		System.out.println("Max: " + maxSum.maxSum());
	}

}

function int maxsum(node root)
{
if(null == root)
{
return 0;
}
maxleft=maxsum(root->left);
maxrt=maxsum(root->right);

if(maxrt>maxleft)
{
return maxrt+root.value;
}
else
{
return maxleft+root.value;
}
}

function int maxsum(node root)
{
if(null == root)
{
return 0;
}
maxleft=maxsum(root->left);
maxrt=maxsum(root->right);

if(maxrt>maxleft)
{
return maxrt+root.value;
}
else
{
return maxleft+root.value;
}
}

its involves maths stuff rather then considering tree (it wont work check below link for detail ) or applying computer science & problem is already famous (Euler problem ) as we have to find the maximum sum in triangle we have given a big triangle which has many small triangle only thing u need to know a triangle has 3 vertexes so that you can approach :)

and a detailed description,explaination & solution you can find here

shashank7s dot blogspot dot com/2011/04/project-euler-problem-67-finding dot html

p.s. remove dot & place . above then concate to remove spaces

let me know if i missed something or any other approach to solve it

Shashank

seems like a DP problem.

Js solution

var arr = [[1], [2, 3] , [5, 6, 17], [20, 30, 400, 50]];
function Tree(depth, value, position){
	this.value = value;	
	
	depth++;
	if(depth >= arr.length){
	    this.max_value = this.value;
		return;
	}
	this.left = new Tree(depth, arr[depth][position], position);
	this.right = new Tree(depth, arr[depth][position + 1], position + 1);	
	this.max_value = this.value + Math.max(this.right.max_value, this.left.max_value);
}
var depth = 0;
tree = new Tree(depth, arr[0][0], 0);
console.log(tree.max_value);

Formula is: n(n+1) / 2 or n(n-1) / 2 + n
Javascript solution:

const maxPathSum = (triangle, depth=0, position=0) => {
  const level = triangle[depth];
  if (level == null) { return 0; }
  
  const leftSum = maxPathSum( triangle, depth+1, position );
  const rightSum = maxPathSum( triangle, depth+1, position+1 );
  
  return level[position] + Math.max( leftSum, rightSum );
}

const triangle = [ [0], [1, 2], [5, 4, 8] ];
console.log( maxPathSum( triangle ) );

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxPathSum = function(root) {
    
    let maxVal = -Infinity;
    findSum(root);
    return maxVal;
    
    function findSum(root) {
        if(root === null) return 0;
        let l = Math.max(findSum(root.left), 0);
        let r = Math.max(findSum(root.right), 0);
        let maxlr = Math.max(l, r);
        let maxSingle = Math.max(maxlr + root.val, root.val );
        let maxAll = Math.max(maxSingle,l + r + root.val);
        maxVal = Math.max.call(null, maxVal, maxSingle, maxAll);
        return maxSingle;
    } 
};