Algorithms and Data Structures

Profound Academy

Course Status
1
🛠️ Implementation
2
0️⃣ Binary Numbers
3
🔟 Bitwise operations
4
🔟 Extracurricular Bitwise operations
5
🔟 Recap
6
➕ Prefix Sums
7
➕ Extracurricular Prefix sum
8
🪟 Sliding window / Two pointers
9
🪟 Recap
10
⏲️ Modular Arithmetic
11
🔢 Number Theory
12
🔢 Extracurricular Number Theory
13
🔍 Binary Search
14
🔍 Extracurricular Binary Search
15
🔍 Recap
16
📶 Basic Sorting
17
📶 Extracurricular Sorting
18
🤑 Greedy Algorithms
19
🤑 Extracurricular Greedy
20
🧨 Basic Dynamic Programming
21
🧨 Extracurricular Dynamic Programming
22
🔄 Recursion
23
🔄 Extracurricular Recursion
24
🪓 Divide & Conquer + Advanced Sorting
25
🪓 Extracurricular Divide and Conquer
26
🪓 Recap
27
🔗 Linked LIst
28
📚 Queue & Stack
29
📚 Extracurricular Queue and Stack
30
🌲 Binary tree and BST
31
🌲 Extracurricular Binary Tree and BST
32
🗼 Heap
33
🗼 Extracurricular Heap
34
#️⃣ Hashing
35
#️⃣ Extracurricular Hashing
36
💣 Advanced Dynamic Programming
37
🔆 Graph Representation
38
🔆 Extracurricular Graph Representation
39
🕸️ BFS
40
🕸️ Extracurricular BFS
41
☸️ DFS
42
☸️ Extracurricular DFS
43
🔱 Trie
44
🔱 Extracurricular Trie
45
🏋‍♂ Dijkstra
46
🏋‍♂ Extracurricular Dijkstra
47
↩️ Backtracking
48
↩️ Extracurricular Backtracking
49
🎄 Segment Tree
50
🎄 Extracurricular Segment Tree

Maximum falling path sum

Given a grid of height h and width w, you are asked to calculate the maximum sum one might obtain by moving from top to bottom, where on each step it’s only allowed to move to the below adjacent 3 cells. In other words, being at position (r, c), you can move to positions: (r + 1, c - 1), (r + 1, c), and (r + 1, c + 1). That’s why we call it a falling sum - as we fall from the top to the very bottom of the grid. Find the maximum sum of the path.

ㅤ	o	ㅤ	ㅤ
↙️	⬇️	↘️	ㅤ
ㅤ	ㅤ	ㅤ	ㅤ
ㅤ	ㅤ	ㅤ	ㅤ

Input

The first line of the input contains two integers h and w (1 ≤ h, w ≤ 100).

The next h lines contain w numbers (-100 ≤ ≤ 100) representing the values of the grid at row r and column c.

Output

The program should print the maximum possible sum obtained among all the possible falling paths.

Examples

Input	Output
3 3 2 1 3 6 5 4 7 8 9	17

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in

Sign in to continue