All Tracks Algorithms Dynamic Programming Introduction to Dynamic Programming 1 Problem

Maximum Chocolate
Tag(s):

Easy-Medium

Problem
Editorial
Analytics

Bharat is chocoholic. He found a chocolate factory of N floors ,but the factory has N*N rooms where in each room specific number of chocolate is present. Now, Bharat starts collecting chocolate from ground floor. He can only collect chocolate from one room in a floor. Bharat can only move to upper room or upper-right room or upper-left room .

He want to collect maximum number of chocolate possible. Help him in finding maximum number of chocolate.

Input:

First line contains a value of N. Next N lines contains N space separated integer.

Output:

Output a single integer denoting the maximum number of chocolate Bharat can collect.

Constraints

1 <= N <= 1000

1 <= Number chocolate in 1 room <= 10^5

SAMPLE INPUT
5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
100 2 3 4 5
SAMPLE OUTPUT
114
Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

Notifications
View All Notifications