5854. Maximum sum basic

There is a rectangular grid of size n rows and m columns. Each cell of the grid contains one integer. You can start the route from any cell of the top row. Each time you can move to one of the “lower neighboring” cells (in other words, from the cell number (i, j) it’s possible to go either to (i + 1, j – 1), or to (i + 1, j) or to (i + 1, j + 1); in the case j = m the last of the three options becomes impossible, in the case j = 1 the first option becomes impossible). And you can finish the route at any cell of the bottom row.

Write a program that finds the maximum possible sum of the values on the cells traversed among all the possible paths.

Input. The first line contains numbers n and m (1 ≤ n, m ≤ 200) – the number of rows and columns. Each of the next n lines contains m integers (each number is no more than 10⁶ by absolute value) – the values of the cells in the grid.

Output. Print one number – the maximum possible sum.

Sample input	Sample output
4 3 1 15 2 9 7 5 9 2 4 6 9 -1	42

SOLUTION

dynamic programming

Algorithm analysis

Let a[i][j] be the input table. Let dp[i][j] stores the maximum sum of numbers on the way from any cell of the first line to cell (i, j). Then

dp[i][j] = max(dp[i – 1][j – 1], dp[i – 1][j], dp[i – 1][j + 1]) + a[i][j]

For the correct calculation of the values of the first and last columns, one should set dp[i][0] = dp[i][m + 1] = -∞.

The first row of the dp array is initialized with the values of the first row of the table а: dp[1][i] = a[1][i], 1 ≤ i ≤ m.

The answer to the problem will be the maximum number in the last (n-th) row of the dp table.

Example

Consider the input sample.

Algorithm realization

Declare a constant – minimum MIN, as well as arrays a and dp.

#define MAX 202

#define MIN -2000000000

int a[MAX][MAX], dp[MAX][MAX];

Read the input data. Store the upper left corner of the input table in a[1][1]. Fill the columns with numbers 0 and m + 1 in the dp array with the minimum possible number MIN.

scanf("%d %d", &n, &m);

for (i = 1; i <= n; i++)

{

dp[i][0] = dp[i][m + 1] = MIN;

for (j = 1; j <= m; j++)

scanf("%d", &a[i][j]);

}

Copy the first line from array a to array dp.

for (i = 1; i <= n; i++)

dp[1][i] = a[1][i];

Recompute the maximum sums on the paths from the top line to the cell (i, j) in the dp array.

for (i = 2; i <= n; i++)

for (j = 1; j <= m; j++)

dp[i][j] = max(max(dp[i - 1][j - 1], dp[i - 1][j]),

dp[i - 1][j + 1]) + a[i][j];

Find the largest number in the last (n-th) row.

res = MIN;

for (i = 1; i <= m; i++)

if (dp[n][i] > res) res = dp[n][i];

Print the answer.

printf("%d\n", res);

Java realization

import java.util.*;

public class Main

{

static int a[][], dp[][];

final static int MIN = -2000000000;

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

int m = con.nextInt();

dp = new int[n+1][m+2];

a = new int[n+1][m+2];

for (int i = 1; i <= n; i++)

{

dp[i][0] = dp[i][m + 1] = MIN;

for (int j = 1; j <= m; j++)

a[i][j] = con.nextInt();;

}

for (int i = 1; i <= m; i++)

dp[1][i] = a[1][i];

for (int i = 2; i <= n; i++)

for (int j = 1; j <= m; j++)

dp[i][j] = Math.max(Math.max(dp[i - 1][j - 1], dp[i - 1][j]), dp[i - 1][j + 1]) + a[i][j];

int res = MIN;

for (int i = 1; i <= m; i++)

if (dp[n][i] > res) res = dp[n][i];

System.out.println(res);

con.close();

}

}