@navin :
/*
*I think the path between two leaves always passes thru root.*
*/
not alwayzz..consider a case where there are 2 leaf node on left side of
the tree.
1
/
5
/ \
10 15
ans :30 ( 5,10,15)
root(1) is not included.
On Wed, Aug 29, 2012 at 1:15 AM, Navin Gupta
@navin
it is not necessary that path b/w two leaves always pass thru root.
On Wed, Aug 29, 2012 at 1:15 AM, Navin Gupta navin.nit...@gmail.com wrote:
I think the path between two leaves always passes thru root.
Now we can keep track of root-to-leaf path whose sum is max and secondMax
among
I think the path between two leaves always passes thru root.
Now we can keep track of root-to-leaf path whose sum is max and secondMax
among all sums.
Now between this two leaves path, root is repeated.
Hence actual sum is maxsum + secondMaxSum - root-val;
This can be done by iterative inorder
I hope using a backtracking solution suits the problem well...
maxsum( int arr[] , int n,int i,int sum, int last)
{
if(in)
{
int s1= 0,s2= 0,s3;
if(last ==i-1)
{
s1=maxsum(arr,n,i+2,sum,last);
}
else
{
s2= maxsum(arr,n,i+1,sum+arr[i],i);
int FindMaxSum(int array[],int i)
{
if(iSize) //Size is array size, considered as global variable in
my solution
return 0;
int Sum1 = FindMaxSum(array,i+2);//cannot chose i+1 as that will
make it adjacent
int Sum2 = FindMaxSum(array,i+3);//at any place I cannot chose i
+1, so I
this can be done easily using dynamic programming:
dp[i] = a[i] + max( dp[i+2], dp[i+3], dp[i+4] , ... )
for (i=n-1 ; i=0 ; i--)
{
max=0;
for (j=i+2 ; jn ;j++)
if (dp[j]max)
max=dp[j];
dp[i]=a[i]+max;
}
On 6/11/10, BALARUKESH sbalarukesh1...@gmail.com wrote:
I hope
