Practice › Dynamic Programming
Maximum Falling Path Sum
Medium · Dynamic Programming · Asked at Google, Amazon, Microsoft
Start in any cell of the first row of the n × n matrix. From (i, j) you may move to (i+1, j−1), (i+1, j) or (i+1, j+1). Print the maximum sum of a path that ends in the last row.
Input
First line: n. Next n lines: n integers.
Output
The maximum falling path sum.
Constraints
- 1 ≤ n ≤ 500
- -100 ≤ values ≤ 100
dp[i][j] = a[i][j] + max(dp[i−1][j−1], dp[i−1][j], dp[i−1][j+1]) (only the in-bounds ones).
Example 1
Input
3 1 2 10 4 5 6 7 8 9
Output
25
Example 2
Input
2 -5 -1 -2 -9
Output
-3
Hints
- A cell in row i can be reached only from row i − 1, columns j − 1, j or j + 1.
- dp[i][j] = a[i][j] + max of those three (ignoring out-of-range columns). Answer = max of the last row.
Approach
Process rows top to bottom keeping the previous row's best sums. For each column, add the cell value to the best of the up-to-three reachable cells above. Use a fresh array per row so values of the current row do not leak into its own neighbours. Values may be negative, so start from the real values, not 0.
Complexity: O(n²) time · O(n) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<long long> dp(n);
for (auto &x : dp) cin >> x;
for (int i = 1; i < n; i++) {
vector<long long> cur(n);
for (int j = 0; j < n; j++) {
long long x;
cin >> x;
long long best = dp[j];
if (j > 0) best = max(best, dp[j - 1]);
if (j < n - 1) best = max(best, dp[j + 1]);
cur[j] = x + best;
}
dp = cur;
}
cout << *max_element(dp.begin(), dp.end()) << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n = data[0]
dp = data[1 : 1 + n]
for i in range(1, n):
row = data[1 + i * n : 1 + (i + 1) * n]
dp = [row[j] + max(dp[max(0, j - 1) : j + 2]) for j in range(n)]
print(max(dp))Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long[] dp = new long[n];
for (int j = 0; j < n; j++) dp[j] = sc.nextLong();
for (int i = 1; i < n; i++) {
long[] cur = new long[n];
for (int j = 0; j < n; j++) {
long x = sc.nextLong(), best = dp[j];
if (j > 0) best = Math.max(best, dp[j - 1]);
if (j < n - 1) best = Math.max(best, dp[j + 1]);
cur[j] = x + best;
}
dp = cur;
}
long ans = Long.MIN_VALUE;
for (long v : dp) ans = Math.max(ans, v);
System.out.println(ans);
}
}Solve Maximum Falling Path Sum online · All practice problems