Nonogram (Picross) linear solution

See more:

time

algorithm

Matrix

I need to solve a nonogram problem. My specific problem is to find the maximum number of points that i can put in a nonogram matrix (no need a graphical solution). My input is a sequence of values that represents the maximum number of points for each row and for each coloumn. For example the sequence 2 2 1 1 1 1 represents a 3x3 matrix in wich the row's values are 2 2 1 and the coloumn's values are 1 1 1. The algorithm should return 3. I know how to implement the quadratic solution, but i need to find a linear time solution or something like linear (for example n log^7(n)).