Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. A cell in row i can be reached only from row i − 1, columns j − 1, j or j + 1.
  2. 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