Question: Given an array of integers.....
Imagine it as a pyramid as below:

a[]={1,2,3,4,5,6,7,8,9,10}
1
2 3
4 5 6
7 8 9 10
find a path from level 1 to last level such that the sum is maximum.... The path is such that its children should be reachable.
Ex:
1,2,5,9 is a path
1,2,6,10 is not a path since 6 is not reachable from 2.
The array is not sorted and numbers are random.


Solution: int sumPath(int[] a, int i){
int length = a.length();
int n = child(i);
if(n+1 < length)
return a[i] + max(sumPath(n), sumPath(n+1));
else if(n < length)
return a[i] + sumPath(n);
else
return a[i];
}

int child(int i){
// function returns #out for a given #in
//example (in,out) pairs: //(0,1), (1,3) (2,4), (3,6), (4,7), (5,8), (6,10), (7,11) etc.
return (1 + sqrt((double)(8*i + 1))) / 2;
}

It works just like a tree, heap in particular, where nodes are stored in a, say a zero based array and its children are accessed by 2i+1 and 2i+2. in case of a pyramid, inner nodes have two parents. so the function to determine children is slightly different.

And sumpath is just like any recursion tree algo, say to find maxdepth at a node.