/*Given grid of positive numbers, strat from (0,0) ad end at (n,n).
   Move only to RIGHT and DOWN. Find path with sum of numbers is maximum. */
 
#include <algorithm>
#include<iostream>
 
const int grid[2][3] = { { 5, 1, 2 }, { 6, 7, 8 } };
 
bool valid (int r, int c)
{
    return r < 2 && c < 3;
}
 
int maxPathSum (int row, int column)
{
    if (!valid (row, column))
        return 0;
 
    if (row == 1 && column == 2) //base condition
        return grid[row][column];
 
    int path1 = maxPathSum (row, column + 1); //Right
    int path2 = maxPathSum (row + 1, column); //Down
 
    return grid[row][column] + std::max(path1, path2);
}
 
int main ()
{
    std::cout << maxPathSum (0, 0) << std::endl;
    return 0;
}
 

LypHaXZlbiBncmlkIG9mIHBvc2l0aXZlIG51bWJlcnMsIHN0cmF0IGZyb20gKDAsMCkgYWQgZW5kIGF0IChuLG4pLgogICBNb3ZlIG9ubHkgdG8gUklHSFQgYW5kIERPV04uIEZpbmQgcGF0aCB3aXRoIHN1bSBvZiBudW1iZXJzIGlzIG1heGltdW0uICovCgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZTxpb3N0cmVhbT4KCmNvbnN0IGludCBncmlkWzJdWzNdID0geyB7IDUsIDEsIDIgfSwgeyA2LCA3LCA4IH0gfTsKCmJvb2wgdmFsaWQgKGludCByLCBpbnQgYykKewogICAgcmV0dXJuIHIgPCAyICYmIGMgPCAzOwp9CgppbnQgbWF4UGF0aFN1bSAoaW50IHJvdywgaW50IGNvbHVtbikKewogICAgaWYgKCF2YWxpZCAocm93LCBjb2x1bW4pKQogICAgICAgIHJldHVybiAwOwoKICAgIGlmIChyb3cgPT0gMSAmJiBjb2x1bW4gPT0gMikgLy9iYXNlIGNvbmRpdGlvbgogICAgICAgIHJldHVybiBncmlkW3Jvd11bY29sdW1uXTsKCiAgICBpbnQgcGF0aDEgPSBtYXhQYXRoU3VtIChyb3csIGNvbHVtbiArIDEpOyAvL1JpZ2h0CiAgICBpbnQgcGF0aDIgPSBtYXhQYXRoU3VtIChyb3cgKyAxLCBjb2x1bW4pOyAvL0Rvd24KCiAgICByZXR1cm4gZ3JpZFtyb3ddW2NvbHVtbl0gKyBzdGQ6Om1heChwYXRoMSwgcGF0aDIpOwp9CgppbnQgbWFpbiAoKQp7CiAgICBzdGQ6OmNvdXQgPDwgbWF4UGF0aFN1bSAoMCwgMCkgPDwgc3RkOjplbmRsOwogICAgcmV0dXJuIDA7Cn0K