Maximum sum of a path in a Right Number Triangle

Difficulty Level Medium
Frequently asked in Citrix DE Shaw Directi Expedia
Dynamic Programming MathViews 1481

The problem “Maximum sum of a path in a Right Number Triangle” states that you are given some integers in the form of a right number triangle. Find out the maximum sum you can achieve if you start from the top and move towards the base such that you move only to the cell just below it or one place to the right of it.

Example

Maximum sum of a path in a Right Number Triangle

3 // Number of rows in the right number triangle
1
3 2
4 10 12

15

Explanation

The maximum sum that can be achieved by moving from the top to the bottom is 15. This can be achieved from the following steps: 1 -> 2 -> 12. It can be better understood from the above image.

Approach

We have already some other problems that are similar to this problem. We had solved problems to find the maximum, minimum sum path in a triangle. This problem is a slight variation of those problems. So the condition which is imposed on the movement is that you can go just below or just right of the current cell. And you start from the top that is from the top vertex. Then reach the bottom.

One way is to use recursion. We will create a function that will take indices as arguments and find the maximum that can be achieved from that cell. This way we recursively find the answer. But this makes the problem time consuming and will surely result in exceeding the time limit. Thus to solve the problem efficiently. We can either memorize the result of these recursive calls. Or use Dynamic Programming to solve this. We will discuss a bottom-up approach which will first compute the result for smaller sub-problems and then combining those results finds the answer for the original problem.

We define the base case, as filling the DP[0][0] with the initial input array’s cell. Because we cannot reach this cell from any other cell and this is the start. after this, we go to the second row. here we have a single option for both of the cells. and the option is to choose the top vertex cell. Then after this row, for all the cells we need to decide which cell to choose that either the just to cell or the cell which is just to the left of the current cell. After all this is done, we take the maximum stored at the last row of the dp table.

Code

C++ code to find the maximum sum of a path in a Right Number Triangle

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n;cin>>n;
    int input[n][n];
    for(int i=0;i<n;i++)
        for(int j=0;j<=i;j++)
            cin>>input[i][j];
  if (n > 1)
    input[1][1] = input[1][1] + input[0][0];
    input[1][0] = input[1][0] + input[0][0];
  for(int i = 2; i < n; i++){
        // because the boundary cells have only a single option
    input[i][0] = input[i][0] + input[i-1][0];
    input[i][i] = input[i][i] + input[i-1][i-1];
    for (int j = 1; j < i; j++)
            input[i][j] = input[i][j] + max(input[i-1][j-1], input[i-1][j]);
  }

  int ans = INT_MIN;
  for(int i=0;i<n;i++)
        ans = max(ans, input[n-1][i]);
  cout<<ans;
}

3
1
3 2
4 10 12
15

Java code to find the maximum sum of a path in a Right Number Triangle

import java.util.*;
class Main{
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int input[][] = new int[n][n];
      for(int i=0;i<n;i++)
          for(int j=0;j<=i;j++)
              input[i][j] = sc.nextInt();;
    if (n > 1)
      input[1][1] = input[1][1] + input[0][0];
      input[1][0] = input[1][0] + input[0][0];
    for(int i = 2; i < n; i++){
          // because the boundary cells have only a single option
      input[i][0] = input[i][0] + input[i-1][0];
      input[i][i] = input[i][i] + input[i-1][i-1];
      for (int j = 1; j < i; j++)
              input[i][j] = input[i][j] + Math.max(input[i-1][j-1], input[i-1][j]);
    }

    int ans = Integer.MIN_VALUE;
    for(int i=0;i<n;i++)
          ans = Math.max(ans, input[n-1][i]);
    System.out.println(ans);
  }
}
3
1
3 2
4 10 12
15

Complexity Analysis

Time Complexity

O(N^2), where N refers to the number of rows in the triangle. Because that is the number of elements that are in the last row.

Space Complexity

O(1), because we use the same input array for DP table. Thus the space complexity is constant because we did not take the space for creating a new DP array.

Translate »