Finding Maximum Sum in Triangle ( excellent Dynamic programming )

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 4
2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.


The problem required us to determine the maximum sum for any given triangle. Also an interesting thing is mentioned about the problem, in case you were considering a brute force method of checking every path:

It is not possible to try every route to solve this problem (where the base of the triangle has 100 numbers), as there are 2^(99) altogether! If you could check one trillion (10^(12)) routes every second it would take over twenty billion years to check them all. There is an efficient algorithm to solve it.

This problem was not as tricky as they tried to sound it. The solution is quite easy to see. I’ll run you through the idea as it formed in my mind. I used the top-to-bottom approach for forming the idea and coming up with the solution, and then implemented the solution in bottom-to-top sweep. I hope you have realized that a greedy solution will not work here.

Consider the triangle given above. I’ll work out the maximum path for it from top to bottom. We start with 3. We may choose either 7 or 4. To help make this choice, consider the two triangles with apex 7 and the other with 4. So we have two smaller triangles of height 3 each. Say the maximum length for the triangle with apex 7 is x and with apex 4 is y. If x > y, we choose 7 as the next on the path, else 4.

Thus, at every step we form two triangle of height 1 smaller, and choose the apex which has the larger sum. Implemented as it is will give us the recursive solution.

input triangle -->

int arr[][]= {{3},
         {7,4},
         {2,4,6},
         {8,5,9,3}};

we create a array according to given  given triangle . and fill the value according .

int array[][]={{0},
           {0,0},
           {0,0,0},
           {0,0,0,0}};

if(j==0)
 array[i][j]=array[i-1][j]+arr[i][j] ;
else
     if(j==array[i].length-1)
         array[i][j] = array[i-1][j-1]+arr[i][j] ;
      else
         array[i][j] = max(array[i-1][j-1],array[i-1][j])+arr[i][j] ;


after this we find the maximum value in the last row . and that is the answer . :D

code ---->

class TriangalSum{

static int max(int a,int b){
return a>b?a:b ;
}

static void maxSum(int arr[][]){

  int max ;
  int array[][]=new int[arr.length][];

for(int i=0;i<arr.length ;i++)
    array[i]= new int[arr[i].length];

  array[0][0]=arr[0][0];

for(int i=1;i<array.length ;i++){
for(int j=0;j<array[i].length ;j++){
 
if(j==0)
array[i][j]=array[i-1][j] + arr[i][j];
else{
  if(j==array[i].length - 1)
     array[i][j]=array[i-1][j-1] + arr[i][j];
 else
    array[i][j] = max(array[i-1][j],array[i-1][j-1]) +arr[i][j] ;

  }
   }
}
max=array[array.length-1][0];

for(int i=1;i<array[array.length-1].length ;i++){
      if(array[array.length-1][i] > max)
  max  = array[array.length-1][i];
}

System.out.println("max sum is =" + max);
  }

public static void main(String s[]){
 
int arr[][]= {{3},
             {7,4},
 {2,4,6},
 {8,5,9,3}};
      maxSum(arr);    
}
}