The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as
well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. Donald E. Knuth

Miscellaneous

Problem :-
Given a triangle in the form of a lower diagonal matrix, find the weight of maximum path in the triangle.
Two possible branches for an element at matrix [ i ][ j ] are matrix [ i+1 ][ j ] & matrix [ i+1 ][ j+1 ].
Consider the triangle :-
2
2 1
3 2 4
5 6 8 6
Maximum weighted path is 2 (matrix[0][0]) + 1 (matrix[1][1]) + 4 (matrix[2][2]) + 8 (matrix[3][2]) = 15

Solution :-
At any cell ( i , j ) of the triangular matrix, we have two possible cells to choose [ ( i + 1 , j ) or ( i + 1 , j + 1 ) ]
We will consider both the options and recursively find out the weights obtained for the paths.
Finally, we return the maximum weighted path. See the implementation below.

#include<iostream>
using namespace std;

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

// compute the max weighted path in a bottom up approach
int computeMaxPath(int triangle[4][4],int size,int i,int j) {
   if(size-1 == i) {
      // boundary case ( single cell matrix )
      return triangle[i][j];
   }
   else {
      // find the max path from two possible branches
      // considering triangle[i][j] as the root
      int a = computeMaxPath(triangle,size,i+1,j);
      int b = computeMaxPath(triangle,size,i+1,j+1);
      return triangle[i][j] + max(a,b);
   }
}

// main
int main() {
   int triangle[4][4] = { {2,0,0,0},
                          {2,1,0,0},
                	  	  {3,2,4,0},
                	  	  {5,6,8,6} };
   // max path = 2+1+4+8 = 15
   int size = 4;
   // last 2 params denote the cell indices in the matrix   
   int path_weight = computeMaxPath(triangle,size,0,0);
   cout<<"\nPath Weight = "<<path_weight;
   cout<<endl;
   return 0;
}

Back | Next

All Miscellaneous Problems
* Print all possible permutation of array elements
* Given the number of parenthesis pairs, print all possible combination of Balanced Parenthesis
* Given a set with 'n' elements, print subsets of all possible sizes
* Given a triangle in the form of a lower diagonal matrix, find the weight of maximum path in the triangle
* Given a matrix of 0s & 1s, find the maximum size square submatrix with all values as 1
* Given a set with 'n' elements. Find the sum of maximum elements in all subsets of size 'p' such that p <= n
* Given 2 strings, find all possible interleaved combination of the characters of the 2 strings