First, if you ignore the condition that you can only pick up at most three in the same row, you can find the answer by a simple Dynamic Programming (DP) (in which \(f_{i, j} := \) the maximum sum on the path from \((1, 1)\) to \((i ,j)\).

By the condition of “at most three,” some of you may think trying all the combinations for each columns, but then at least information of the left and right end seems to be needed to store, so it needs cubic time complexity.

However, we can add the infromation of how many times has they been picked up in the current (\(i\)-th) row and calculate \(f_{i,j,k}\), then for each \(i,j,k\) there are only \(O(1)\) number of transitions (in which \(k\) is reset to \(k=0\) when moving to \(i+1\), or if \(i\) remains unchanged, original \(k\) is inherited), so the overall DP can be calculated in a total of \(O(NM)\) time.

Likewise, in the problem where you are asked to choose a constant number of elements from a segment, it may possible to optimize it by storing the state of the segment as an additional state.

Sample Code(C++)