# 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``

## 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

© 2022, kalkicode.com, All rights reserved