Skip to main content

Maximum path sum in a triangle

Here given code implementation process.

/*
    Java program for
    Maximum path sum in a triangle
*/
public class Path
{

    public int maxValue(int a, int b)
    {
        if(a > b)
        {
            return a;
        }
        return b;
    }
    public void maxPath(int [][]triangle)
    {
       int n = triangle.length;
       int m = triangle[0].length;
       int k = m-2;

       // Auxiliary space
       int [][]dp = new int[n][m];

        // Copy triangle element
        for (int i = 0; i < n  ; ++i ) 
        {
            for (int j = 0; j < m ; ++j ) 
            {
                dp[i][j] = triangle[i][j];       
            }    
        } 


        for ( int r = n-2; r >= 0 ; r-- ) 
        {
            for (int c = k; c >= 0 ; c-- ) 
            {
                if(c > 0)
                {
                    // Set max value of current element and 
                    // combination of bottom element.
                    // Bottom element is combination of three elements
                    dp[r][c] = maxValue(
                        maxValue(dp[r+1][c-1] + dp[r][c],
                            dp[r+1][c] + dp[r][c]), 
                                dp[r+1][c+1] + dp[r][c]);
                } 
                else
                {
                    // Two bottom element are used
                    dp[r][c] = maxValue(dp[r+1][c] + dp[r][c],
                                        dp[r+1][c+1] + dp[r][c]);
                }   
            }    
            k--;
        }

        System.out.println(dp[0][0]);
    }
 
    public static void main(String[] args)
    {
        Path task = new Path();
        
        int [][]triangle = 
        {  
            {1,  0, 0, 0, 0}, 
            {-2, 1, 0, 0, 0},
            {7,  3, 4, 0, 0},
            {5,  4, 2, 3, 0},
            {1,  1, 3, 3, 0}
        };
        /*
            {1,  -,  -, -, -}, 
              ⤡
            {-, 1,   -, -, -},
              ⤢
            {7,  -,  -, -, -},
               ⤡
            {-,  4,  -, -, -},
                   ⤡
            {-,  -,  3, -, -}
            -----------------------
            1 + 1 + 7 + 4 + 3 = 16
        */
        task.maxPath(triangle);
    }
}

Output

16
// Include header file
#include <iostream>
#define N 5
using namespace std;
/*
    C++ program for
    Maximum path sum in a triangle
*/
class Path
{
    public: int maxValue(int a, int b)
    {
        if (a > b)
        {
            return a;
        }
        return b;
    }
    void maxPath(int triangle[N][N])
    {
        int k = N - 2;
        // Auxiliary space
        int dp[N][N];
        // Copy triangle element
        for (int i = 0; i < N; ++i)
        {
            for (int j = 0; j < N; ++j)
            {
                dp[i][j] = triangle[i][j];
            }
        }
        for (int r = N - 2; r >= 0; r--)
        {
            for (int c = k; c >= 0; c--)
            {
                if (c > 0)
                {
                    // Set max value of current element and 
                    // combination of bottom element.
                    // Bottom element is combination of three elements
                    dp[r][c] = this->maxValue(
                      this->maxValue(dp[r + 1][c - 1] + dp[r][c], 
                                     dp[r + 1][c] + dp[r][c]), 
                      dp[r + 1][c + 1] + dp[r][c]);
                }
                else
                {
                    // Two bottom element are used
                    dp[r][c] = this->maxValue(dp[r + 1][c] + dp[r][c], 
                                              dp[r + 1][c + 1] + dp[r][c]);
                }
            }
            k--;
        }
        cout << dp[0][0] << endl;
    }
};
int main()
{
    Path *task = new Path();
    int triangle[N][N] = 
    {  
        {1,  0, 0, 0, 0}, 
        {-2, 1, 0, 0, 0},
        {7,  3, 4, 0, 0},
        {5,  4, 2, 3, 0},
        {1,  1, 3, 3, 0}
    };
    /*
        {1,  -,  -, -, -}, 
          ⤡
        {-, 1,   -, -, -},
          ⤢
        {7,  -,  -, -, -},
           ⤡
        {-,  4,  -, -, -},
               ⤡
        {-,  -,  3, -, -}
        -----------------------
        1 + 1 + 7 + 4 + 3 = 16
    */
    task->maxPath(triangle);
    return 0;
}

Output

16
// Include namespace system
using System;
/*
    Csharp program for
    Maximum path sum in a triangle
*/
public class Path
{
	public int maxValue(int a, int b)
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	public void maxPath(int[,] triangle)
	{
		int n = triangle.GetLength(0);
		int m = triangle.GetLength(1);
		int k = m - 2;
		// Auxiliary space
		int[,] dp = new int[n,m];
		// Copy triangle element
		for (int i = 0; i < n; ++i)
		{
			for (int j = 0; j < m; ++j)
			{
				dp[i,j] = triangle[i,j];
			}
		}
		for (int r = n - 2; r >= 0; r--)
		{
			for (int c = k; c >= 0; c--)
			{
				if (c > 0)
				{
					// Set max value of current element and 
					// combination of bottom element.
					// Bottom element is combination of three elements
					dp[r,c] = this.maxValue(
                      this.maxValue(dp[r + 1,c - 1] + dp[r,c], 
                                    dp[r + 1,c] + dp[r,c]), 
                      dp[r + 1,c + 1] + dp[r,c]);
				}
				else
				{
					// Two bottom element are used
					dp[r,c] = this.maxValue(
                      dp[r + 1,c] + dp[r,c], 
                      dp[r + 1,c + 1] + dp[r,c]);
				}
			}
			k--;
		}
		Console.WriteLine(dp[0,0]);
	}
	public static void Main(String[] args)
	{
		Path task = new Path();
		int[,] triangle = {
			{
				1 , 0 , 0 , 0 , 0
			},
			{
				-2 , 1 , 0 , 0 , 0
			},
			{
				7 , 3 , 4 , 0 , 0
			},
			{
				5 , 4 , 2 , 3 , 0
			},
			{
				1 , 1 , 3 , 3 , 0
			}
		};
		/*
		    [1,  -,  -, -, -] 
		      ⤡
		    [-, 1,   -, -, -]
		      ⤢
		    [7,  -,  -, -, -]
		       ⤡
		    [-,  4,  -, -, -]
		           ⤡
		    [-,  -,  3, -, -]
		    -----------------------
		    1 + 1 + 7 + 4 + 3 = 16
		*/
		task.maxPath(triangle);
	}
}

Output

16
package main
import "fmt"
/*
    Go program for
    Maximum path sum in a triangle
*/

func maxValue(a, b int) int {
	if a > b {
		return a
	}
	return b
}
func maxPath(triangle[][] int) {
	var n int = len(triangle)
	var m int = len(triangle[0])
	var k int = m - 2
	// Auxiliary space
	var dp = make([][] int, n)
	for i:= 0;i < n;i++{
		dp[i] = make([]int,m)
	}
	// Copy triangle element
	for i := 0 ; i < n ; i++ {
		for j := 0 ; j < m ; j++ {
			dp[i][j] = triangle[i][j]
		}
	}
	for r := n - 2 ; r >= 0 ; r-- {
		for c := k ; c >= 0 ; c-- {
			if c > 0 {
				// Set max value of current element and 
				// combination of bottom element.
				// Bottom element is combination of three elements
				dp[r][c] = maxValue(
					maxValue(dp[r + 1][c - 1] + dp[r][c], 
						dp[r + 1][c] + dp[r][c]), 
					dp[r + 1][c + 1] + dp[r][c])
			} else {
				// Two bottom element are used
				dp[r][c] = maxValue(
					dp[r + 1][c] + dp[r][c], 
					dp[r + 1][c + 1] + dp[r][c])
			}
		}
		k--
	}
	fmt.Println(dp[0][0])
}
func main() {

	var triangle = [][] int { 
            {1,  0, 0, 0, 0}, 
            {-2, 1, 0, 0, 0},
            {7,  3, 4, 0, 0},
            {5,  4, 2, 3, 0},
            {1,  1, 3, 3, 0},
        }
	/*
	    [1,  -,  -, -, -] 
	      ⤡
	    [-, 1,   -, -, -]
	      ⤢
	    [7,  -,  -, -, -]
	       ⤡
	    [-,  4,  -, -, -]
	           ⤡
	    [-,  -,  3, -, -]
	    -----------------------
	    1 + 1 + 7 + 4 + 3 = 16
	*/
	maxPath(triangle)
}

Output

16
<?php
/*
    Php program for
    Maximum path sum in a triangle
*/
class Path
{
	public	function maxValue($a, $b)
	{
		if ($a > $b)
		{
			return $a;
		}
		return $b;
	}
	public	function maxPath($triangle)
	{
		$n = count($triangle);
		$m = count($triangle[0]);
		$k = $m - 2;
		// Auxiliary space
		$dp = array_fill(0, $n, array_fill(0, $m, 0));
		// Copy triangle element
		for ($i = 0; $i < $n; ++$i)
		{
			for ($j = 0; $j < $m; ++$j)
			{
				$dp[$i][$j] = $triangle[$i][$j];
			}
		}
		for ($r = $n - 2; $r >= 0; $r--)
		{
			for ($c = $k; $c >= 0; $c--)
			{
				if ($c > 0)
				{
					// Set max value of current element and 
					// combination of bottom element.
					// Bottom element is combination of three elements
					$dp[$r][$c] = $this->maxValue(
                      $this->maxValue($dp[$r + 1][$c - 1] + $dp[$r][$c], 
                                      $dp[$r + 1][$c] + $dp[$r][$c]), 
                      $dp[$r + 1][$c + 1] + $dp[$r][$c]);
				}
				else
				{
					// Two bottom element are used
					$dp[$r][$c] = $this->maxValue(
                      $dp[$r + 1][$c] + $dp[$r][$c], 
                      $dp[$r + 1][$c + 1] + $dp[$r][$c]);
				}
			}
			$k--;
		}
		echo($dp[0][0].
			"\n");
	}
}

function main()
{
	$task = new Path();
	$triangle = array(
      array(1, 0, 0, 0, 0), 
      array(-2, 1, 0, 0, 0), 
      array(7, 3, 4, 0, 0), 
      array(5, 4, 2, 3, 0), 
      array(1, 1, 3, 3, 0)
    );
	/*
	    [1,  -,  -, -, -] 
	      ⤡
	    [-, 1,   -, -, -]
	      ⤢
	    [7,  -,  -, -, -]
	       ⤡
	    [-,  4,  -, -, -]
	           ⤡
	    [-,  -,  3, -, -]
	    -----------------------
	    1 + 1 + 7 + 4 + 3 = 16
	*/
	$task->maxPath($triangle);
}
main();

Output

16
/*
    Node JS program for
    Maximum path sum in a triangle
*/
class Path
{
	maxValue(a, b)
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	maxPath(triangle)
	{
		var n = triangle.length;
		var m = triangle[0].length;
		var k = m - 2;
		// Auxiliary space
		var dp = Array(n).fill(0).map(() => new Array(m).fill(0));
		// Copy triangle element
		for (var i = 0; i < n; ++i)
		{
			for (var j = 0; j < m; ++j)
			{
				dp[i][j] = triangle[i][j];
			}
		}
		for (var r = n - 2; r >= 0; r--)
		{
			for (var c = k; c >= 0; c--)
			{
				if (c > 0)
				{
					// Set max value of current element and 
					// combination of bottom element.
					// Bottom element is combination of three elements
					dp[r][c] = this.maxValue(
                      this.maxValue(dp[r + 1][c - 1] + dp[r][c], 
                                    dp[r + 1][c] + dp[r][c]), 
                      dp[r + 1][c + 1] + dp[r][c]);
				}
				else
				{
					// Two bottom element are used
					dp[r][c] = this.maxValue(
                      dp[r + 1][c] + dp[r][c], 
                      dp[r + 1][c + 1] + dp[r][c]
                    );
				}
			}
			k--;
		}
		console.log(dp[0][0]);
	}
}

function main()
{
	var task = new Path();
	var triangle = [
		[1, 0, 0, 0, 0],
		[-2, 1, 0, 0, 0],
		[7, 3, 4, 0, 0],
		[5, 4, 2, 3, 0],
		[1, 1, 3, 3, 0]
	];
	/*
	    [1,  -,  -, -, -] 
	      ⤡
	    [-, 1,   -, -, -]
	      ⤢
	    [7,  -,  -, -, -]
	       ⤡
	    [-,  4,  -, -, -]
	           ⤡
	    [-,  -,  3, -, -]
	    -----------------------
	    1 + 1 + 7 + 4 + 3 = 16
	*/
	task.maxPath(triangle);
}
main();

Output

16
#    Python 3 program for
#    Maximum path sum in a triangle
class Path :
	def maxValue(self, a, b) :
		if (a > b) :
			return a
		
		return b
	
	def maxPath(self, triangle) :
		n = len(triangle)
		m = len(triangle[0])
		k = m - 2
		#  Auxiliary space
		dp = [[0] * (m) for _ in range(n) ]
		i = 0
		#  Copy triangle element
		while (i < n) :
			j = 0
			while (j < m) :
				dp[i][j] = triangle[i][j]
				j += 1
			
			i += 1
		
		r = n - 2
		while (r >= 0) :
			c = k
			while (c >= 0) :
				if (c > 0) :
					#  Set max value of current element and 
					#  combination of bottom element.
					#  Bottom element is combination of three elements
					dp[r][c] = self.maxValue(
                      self.maxValue(dp[r + 1][c - 1] + dp[r][c], 
                                    dp[r + 1][c] + dp[r][c]), 
                      dp[r + 1][c + 1] + dp[r][c])
				else :
					#  Two bottom element are used
					dp[r][c] = self.maxValue(dp[r + 1][c] + dp[r][c], 
                                             dp[r + 1][c + 1] + dp[r][c])
				
				c -= 1
			
			k -= 1
			r -= 1
		
		print(dp[0][0])
	

def main() :
	task = Path()
	triangle = [
		[1, 0, 0, 0, 0],
		[-2, 1, 0, 0, 0],
		[7, 3, 4, 0, 0],
		[5, 4, 2, 3, 0],
		[1, 1, 3, 3, 0]
	]
	#    [1,  -,  -, -, -] 
	#      ⤡
	#    [-, 1,   -, -, -]
	#      ⤢
	#    [7,  -,  -, -, -]
	#       ⤡
	#    [-,  4,  -, -, -]
	#           ⤡
	#    [-,  -,  3, -, -]
	#    -----------------------
	#    1 + 1 + 7 + 4 + 3 = 16
	task.maxPath(triangle)

if __name__ == "__main__": main()

Output

16
#    Ruby program for
#    Maximum path sum in a triangle
class Path 
	def maxValue(a, b) 
		if (a > b) 
			return a
		end

		return b
	end

	def maxPath(triangle) 
		n = triangle.length
		m = triangle[0].length
		k = m - 2
		#  Auxiliary space
		dp = Array.new(n) {Array.new(m) {0}}
		i = 0
		#  Copy triangle element
		while (i < n) 
			j = 0
			while (j < m) 
				dp[i][j] = triangle[i][j]
				j += 1
			end

			i += 1
		end

		r = n - 2
		while (r >= 0) 
			c = k
			while (c >= 0) 
				if (c > 0) 
					#  Set max value of current element and 
					#  combination of bottom element.
					#  Bottom element is combination of three elements
					dp[r][c] = self.maxValue(
                      self.maxValue(dp[r + 1][c - 1] + dp[r][c], 
                                    dp[r + 1][c] + dp[r][c]), 
                      dp[r + 1][c + 1] + dp[r][c])
				else
 
					#  Two bottom element are used
					dp[r][c] = self.maxValue(
                      dp[r + 1][c] + dp[r][c], 
                      dp[r + 1][c + 1] + dp[r][c])
				end

				c -= 1
			end

			k -= 1
			r -= 1
		end

		print(dp[0][0], "\n")
	end

end

def main() 
	task = Path.new()
	triangle = [
		[1, 0, 0, 0, 0],
		[-2, 1, 0, 0, 0],
		[7, 3, 4, 0, 0],
		[5, 4, 2, 3, 0],
		[1, 1, 3, 3, 0]
	]
	#    [1,  -,  -, -, -] 
	#      ⤡
	#    [-, 1,   -, -, -]
	#      ⤢
	#    [7,  -,  -, -, -]
	#       ⤡
	#    [-,  4,  -, -, -]
	#           ⤡
	#    [-,  -,  3, -, -]
	#    -----------------------
	#    1 + 1 + 7 + 4 + 3 = 16
	task.maxPath(triangle)
end

main()

Output

16

/*
    Scala program for
    Maximum path sum in a triangle
*/
class Path()
{
	def maxValue(a: Int, b: Int): Int = {
		if (a > b)
		{
			return a;
		}
		return b;
	}
	def maxPath(triangle: Array[Array[Int]]): Unit = {
		var n: Int = triangle.length;
		var m: Int = triangle(0).length;
		var k: Int = m - 2;
		// Auxiliary space
		var dp: Array[Array[Int]] = Array.fill[Int](n, m)(0);
		var i: Int = 0;
		// Copy triangle element
		while (i < n)
		{
			var j: Int = 0;
			while (j < m)
			{
				dp(i)(j) = triangle(i)(j);
				j += 1;
			}
			i += 1;
		}
		var r: Int = n - 2;
		while (r >= 0)
		{
			var c: Int = k;
			while (c >= 0)
			{
				if (c > 0)
				{
					// Set max value of current element and 
					// combination of bottom element.
					// Bottom element is combination of three elements
					dp(r)(c) = maxValue(
                      maxValue(dp(r + 1)(c - 1) + dp(r)(c), 
                               dp(r + 1)(c) + dp(r)(c)), 
                      dp(r + 1)(c + 1) + dp(r)(c));
				}
				else
				{
					// Two bottom element are used
					dp(r)(c) = maxValue(
                      dp(r + 1)(c) + dp(r)(c), 
                      dp(r + 1)(c + 1) + dp(r)(c));
				}
				c -= 1;
			}
			k -= 1;
			r -= 1;
		}
		println(dp(0)(0));
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Path = new Path();
		var triangle: Array[Array[Int]] = Array(
          Array(1, 0, 0, 0, 0), 
          Array(-2, 1, 0, 0, 0), 
          Array(7, 3, 4, 0, 0), 
          Array(5, 4, 2, 3, 0), 
          Array(1, 1, 3, 3, 0)
        );
		/*
		    [1,  -,  -, -, -] 
		      ⤡
		    [-, 1,   -, -, -]
		      ⤢
		    [7,  -,  -, -, -]
		       ⤡
		    [-,  4,  -, -, -]
		           ⤡
		    [-,  -,  3, -, -]
		    -----------------------
		    1 + 1 + 7 + 4 + 3 = 16
		*/
		task.maxPath(triangle);
	}
}

Output

16
import Foundation;
/*
    Swift 4 program for
    Maximum path sum in a triangle
*/
class Path
{
	func maxValue(_ a: Int, _ b: Int) -> Int
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	func maxPath(_ triangle: [
		[Int]
	])
	{
		let n: Int = triangle.count;
		let m: Int = triangle[0].count;
		var k: Int = m - 2;
		// Auxiliary space
		var dp: [
			[Int]
		] = Array(repeating: Array(repeating: 0, count: m), count: n);
		var i: Int = 0;
		// Copy triangle element
		while (i < n)
		{
			var j: Int = 0;
			while (j < m)
			{
				dp[i][j] = triangle[i][j];
				j += 1;
			}
			i += 1;
		}
		var r: Int = n - 2;
		while (r >= 0)
		{
			var c: Int = k;
			while (c >= 0)
			{
				if (c > 0)
				{
					// Set max value of current element and 
					// combination of bottom element.
					// Bottom element is combination of three elements
					dp[r][c] = 
                      self.maxValue(
                      	self.maxValue(dp[r + 1][c - 1] + dp[r][c], 
                                      dp[r + 1][c] + dp[r][c]), 
                      dp[r + 1][c + 1] + dp[r][c]);
				}
				else
				{
					// Two bottom element are used
					dp[r][c] = self.maxValue(dp[r + 1][c] + dp[r][c], 
                                             dp[r + 1][c + 1] + dp[r][c]);
				}
				c -= 1;
			}
			k -= 1;
			r -= 1;
		}
		print(dp[0][0]);
	}
}
func main()
{
	let task: Path = Path();
	let triangle: [
		[Int]
	] = [
		[1, 0, 0, 0, 0],
		[-2, 1, 0, 0, 0],
		[7, 3, 4, 0, 0],
		[5, 4, 2, 3, 0],
		[1, 1, 3, 3, 0]
	];
	/*
	    [1,  -,  -, -, -] 
	      ⤡
	    [-, 1,   -, -, -]
	      ⤢
	    [7,  -,  -, -, -]
	       ⤡
	    [-,  4,  -, -, -]
	           ⤡
	    [-,  -,  3, -, -]
	    -----------------------
	    1 + 1 + 7 + 4 + 3 = 16
	*/
	task.maxPath(triangle);
}
main();

Output

16
/*
    Kotlin program for
    Maximum path sum in a triangle
*/
class Path
{
	fun maxValue(a: Int, b: Int): Int
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	fun maxPath(triangle: Array < Array < Int >> ): Unit
	{
		val n: Int = triangle.count();
		val m: Int = triangle[0].count();
		var k: Int = m - 2;
		// Auxiliary space
		val dp: Array < Array < Int >> = Array(n)
		{
			Array(m)
			{
				0
			}
		};
		var i: Int = 0;
		// Copy triangle element
		while (i < n)
		{
			var j: Int = 0;
			while (j < m)
			{
				dp[i][j] = triangle[i][j];
				j += 1;
			}
			i += 1;
		}
		var r: Int = n - 2;
		while (r >= 0)
		{
			var c: Int = k;
			while (c >= 0)
			{
				if (c > 0)
				{
					// Set max value of current element and 
					// combination of bottom element.
					// Bottom element is combination of three elements
					dp[r][c] = this.maxValue(
                      this.maxValue(dp[r + 1][c - 1] + dp[r][c], 
                                    dp[r + 1][c] + dp[r][c]), 
                      dp[r + 1][c + 1] + dp[r][c]);
				}
				else
				{
					// Two bottom element are used
					dp[r][c] = this.maxValue(
                      dp[r + 1][c] + dp[r][c], 
                      dp[r + 1][c + 1] + dp[r][c]);
				}
				c -= 1;
			}
			k -= 1;
			r -= 1;
		}
		println(dp[0][0]);
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Path = Path();
	val triangle: Array < Array < Int >> = arrayOf(
      arrayOf(1, 0, 0, 0, 0), 
      arrayOf(-2, 1, 0, 0, 0), 
      arrayOf(7, 3, 4, 0, 0), 
      arrayOf(5, 4, 2, 3, 0), 
      arrayOf(1, 1, 3, 3, 0)
    );
	/*
	    [1,  -,  -, -, -] 
	      ⤡
	    [-, 1,   -, -, -]
	      ⤢
	    [7,  -,  -, -, -]
	       ⤡
	    [-,  4,  -, -, -]
	           ⤡
	    [-,  -,  3, -, -]
	    -----------------------
	    1 + 1 + 7 + 4 + 3 = 16
	*/
	task.maxPath(triangle);
}

Output

16
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment