Maximum cost path in integer matrix In preparation for my design and algorithms exam, I encountered the following problem.


  Given a $2  \times N$ integer  matrix $(a[i][j] \in [-1000, 1000])$ and an unsigned integer $k$, find the maximum cost path from the top left corner $(a[1][1])$ and the bottom right corner $a[2][N]$, given the following:




$\bullet$ The path may not go through the same element more than once

$\bullet$ You can move from one cell to the other vertically or horizontally

$\bullet$ The path may not contain more than $k$ consecutive elements from the same line

$\bullet$ The cost of the path is determined by the sum of all the values stored within the cells it passes through



I've been thinking of a simple greedy approach that seems to work for the test cases I've tried, but I'm not sure if it's always optimal. Namely, while traversing the matrix, I select a the maximum cost cell on the vertical or horizontal and then go from there. I've got a counter I only increment if the current cell is on the same line with the previously examined one and reset it otherwise. If at some point the selected element happens to be one that makes the counter go over the given value of $k$, I simply go with the other option that's left.

However, I feel that I'm missing out on something terribly important here, but I just can't see what. Is there some known algorithm or approach that may be used here? 

Also, the problem asks for an optimal solution (regarding temporal complexity).
This problem was basically made for dynamic programming (DP). Just review it and follow a couple of examples and solving this problem is straight-forward.

Your simple greedy approach does not always work. Consider:

[ begin ] [  2 ]
[ 3 ]     [ 10 ]
[ 1 ]     [ -1000 ]
[ 1 ]     [ end ]


The optimal solution would be to go right, down, left, down, down, right.