Let's assume we want max amount of liars. Let us have a vertex for each prefix of our sequence (also the empty one, so N+1 in total, numbered from 0 to N).

If there's a hint that on the segment [i,j] there are d liars, then add edges (i-1,j) with cost d, and (j,i-1) with cost -d.

We can see that if there's a path from x-1 to y with cost c, it means that our constraints imply that on [x,y] there are c liars. This means that if there were a path from 0 to N then the amount of liars would be known exactly, but there might be no such path.

So, in addition we add edges (i,i+1) with cost 1 (we could get at most one new liar), and (i+1,i) with cost 0 (we could lose no liars).

Lengths of all paths from 0 to N give some upper-bounds on the answer. It's not trivial, but you can prove the tightest one (which is the smallest) can be achieved (in other words - our edges express all the constraints that there are).

Doing min is analogous - just swap liars and non-liars.