Problem Statement -
Given a 2xN grid of numbers, the task is to find the most profitable tiling combination (each tile covers 2x1 cells; vertically or horizontally) covering all tiles.
I thought of approaching it in the greedy way, enqueuing the max possible for any cell, but it has a fallback that a low-profit choice at i, could yield a greater profit at i+n tiles.
So what should be the approach?
EDIT - Test Data Range - N<=105
Source - INOI 2008 Q Paper
UPDATE - Working out the plausibility of a Dynamic programming Approach.
UPDATE 2 - Worked out an answer using DP.