Maximum path sum in a triangle
Given a triangle of numbers, find the maximum possible sum of a path from the top to the bottom of the triangle. A path starts at the top and moves downwards to adjacent numbers on the row below until it reaches the bottom row.
Solution
The given code provides a Java implementation to find the maximum path sum in a triangle. The algorithm uses dynamic programming to efficiently compute the maximum sum.
The main idea behind the solution is to start from the second-to-last row and iterate upwards to the top row. For each element in a row, we calculate the maximum sum by considering the element itself and the maximum sums of the two adjacent elements in the row below.
The algorithm uses a two-dimensional array called "dp" to store the intermediate results. Each element dp[i][j] represents the maximum sum achievable from the top to that element in the triangle.
The algorithm proceeds as follows:
- First, we copy the elements of the triangle into the dp array.
- We start from the second-to-last row and iterate upwards.
- For each element dp[r][c], where r is the current row and c is the column index:
- If c > 0, we calculate the maximum sum by considering the element itself and the maximum sums of the two adjacent elements in the row below: dp[r][c] = max(dp[r+1][c-1] + dp[r][c], dp[r+1][c] + dp[r][c], dp[r+1][c+1] + dp[r][c]).
- If c = 0, we can only consider the two adjacent elements in the row below: dp[r][c] = max(dp[r+1][c] + dp[r][c], dp[r+1][c+1] + dp[r][c]).
- Finally, the maximum path sum is stored in dp[0][0], which represents the top element of the triangle.
Code Solution
/*
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
16package 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
16import 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
16In the provided example, the triangle has the following structure:
1
-2 1
7 3 4
5 4 2 3
1 1 3 3
By following the calculated maximum sums, the maximum path is determined as follows: 1 + 1 + 7 + 4 + 3 = 16.
Time Complexity
The time complexity of the algorithm is O(n^2), where n is the number of rows in the triangle. This is because we iterate through each element in the triangle and perform constant time operations for each element. Since the triangle has n*(n+1)/2 elements, the overall time complexity is O(n^2).
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