Remove the mininum sum seam from an array The seam carving algorithm, or a more complex version of it, is used for content-aware image resizing in various graphics programs and libraries. Let's golf it!

Your input will be a rectangular two dimensional array of integers.

Your output will be the same array, one column narrower, with one entry removed from each row, those entries representing a path from top to bottom with the lowest sum of all such paths.


https://en.wikipedia.org/wiki/Seam_carving

In the above illustration, each cell's value is shown in red. The black numbers are the sum of a cell's value and the lowest black number in one of the three cells above it (pointed to by the green arrows). The white highlighted paths are the two lowest sum paths, both with a sum of 5 (1+2+2 and 2+2+1).

In a case where there are two paths tied for the lowest sum, it does not matter which you remove.

Input should be taken from stdin or as a function parameter. It can be formatted in a manner convenient to your language of choice, including brackets and/or delimiters. Please specify in your answer how the input is expected.

Output should be to stdout in an unambiguously delimited format, or as a function return value in your language's equivalent to a 2d array (which might include nested lists, etc).

Examples:

Input:
1 4 3 5 2
3 2 5 2 3
5 2 4 2 1
Output:
4 3 5 2      1 4 3 5
3 5 2 3  or  3 2 5 3
5 4 2 1      5 2 4 2

Input:
1 2 3 4 5
Output:
2 3 4 5

Input:
1
2
3
Output:
(empty, null, a sentinel non-array value, a 0x3 array, or similar)


EDIT: The numbers will all be non-negative, and every possible seam will have a sum that fits in a signed 32 bit integer.
Haskell, 187 bytes

l=length
f a@(b:c)=snd$maximum$(zip=&lt;&lt;map(sum.concat))$map(zipWith((uncurry((.drop 1).(++)).).flip splitAt)a)$iterate((\e@(f:_)-&gt;[f-1:e,f:e,min(f+1)(l b-1):e])=&lt;&lt;)[[y]|y&lt;-[0..l b-1]]!!l c


Usage example:

*Main&gt; f [[1,4,3,5,2],[3,2,5,2,3],[5,2,4,2,1]]
[[4,3,5,2],[3,5,2,3],[5,4,2,1]]

*Main&gt; f [[1],[2],[3]]
[[],[],[]]

*Main&gt; f [[1,2,3,4,5]]
[[2,3,4,5]]


How it works, short version: build a list of all paths (1), per path: remove corresponding elements (2) and sum all remaining elements (3). Take the rectangle with the largest sum (4).

Longer version:

Input parameters, assigned via pattern matching:
a = whole input, e.g. [[1,2,4],[2,5,6],[3,1,6]]
b = first line, e.g. [1,2,4]
c = all lines, except first, e.g. [[2,5,6],[3,1,6]]

Step (1), build all paths:

iterate((\e@(f:_)-&gt;[f-1:e,f:e,min(f+1)(l b-1):e])=&lt;&lt;)[[y]|y&lt;-[0..l b-1]]!!l c

     [[y]|y&lt;-[0..l b-1]]           # build a list of single element lists
                                   # for all numbers from 0 to length b - 1
                                   # e.g. [[0],[1],[2]] for a 3 column input.
                                   # These are all possible start points

     \e@(f:_)-&gt;[f-1:e,f:e,min(f+1)(l b-1):e]
                                   # expand a list of paths by replacing each
                                   # path with 3 new paths (up-left, up, up-right)

     (...)=&lt;&lt;                      # flatten the list of 3-new-path lists into
                                   # a single list

     iterate (...) [...] !! l c    # repeatedly apply the expand function to
                                   # the start list, all in all (length c) times.


Step (2), remove elements

map(zipWith((uncurry((.drop 1).(++)).).flip splitAt)a)

     (uncurry((.drop 1).(++)).).flip splitAt
                                   # point-free version of a function that removes
                                   # an element at index i from a list by
                                   # splitting it at index i, and joining the
                                   # first part with the tail of the second part

      map (zipWith (...) a) $ ...  # per path: zip the input list and the path with
                                   # the remove-at-index function. Now we have a list
                                   # of rectangles, each with a path removed

Step (3), sum remaining elements

zip=&lt;&lt;map(sum.concat)             # per rectangle: build a pair (s, rectangle)
                                  # where s is the sum of all elements


Step (4), take maximum

snd$maximum                      # find maximum and remove the sum part from the
                                 # pair, again.