C++

#include <iostream> #include <vector> using namespace std; using Matrix = vector< vector <int > >; int maxsum( const Matrix & m, size_t r, size_t c) { if ( c == m[r].size()-1) return m[r][c]; int contrib = maxsum( m,r, c+1); //same row contribution if ( r == 0) contrib = max( contrib, maxsum( m, r+1, c+1)); else if ( r == m.size()-1) contrib = max( contrib, maxsum(m, r-1, c+1)); else contrib = max( contrib, max( maxsum(m, r+1, c+1), maxsum(m, r-1, c+1))); return (m[r][c] + contrib); } int main() { size_t R,C; // R rows, C columns cin >> R >> C; vector < vector <int> > m(R); for (auto & v : m) for (size_t c = 0; c < C; ++c) { int i; cin >> i; v.push_back(i); } int maxgold = 0; for (size_t r = 0; r < R; ++r) { int gold = maxsum(m, r, 0); if (maxgold < gold) maxgold = gold; } cout << "max gold = " << maxgold << endl; }