function [boundaries,levels,totalllh] = dpllh(A,k);

% the error of the best solution for piecewise
% constant representation of 0-1 vector A 
% using k pieces

if (k<1) 
    best = NaN;
    boundaries = NaN;
    return
end

[m,n] = size(A);

    
for i=1:n
    lastpiece(1,i,1) = 1;
    for j=i:n
        cumllh(i,j,1) = llh(A(i:j),i,j);
    end
end

for b=2:k
    for i=1:n
        cumllh(1,i,b) = cumllh(1,i,b-1);
        lastpiece(1,i,b) = -1;
        for j=1:i-1
            if cumllh(1,j,b-1)+cumllh(j+1,i,1)>cumllh(1,i,b)
                cumllh(1,i,b) = cumllh(1,j,b-1)+cumllh(j+1,i,1);
                lastpiece(1,i,b) = j+1;
            end
        end
    end
end


totalllh = 0;
ind = n+1;
boundaries(k+1) = n;

while ind > 0 && k>0
    prevind = ind; 
    ind = lastpiece(1,ind-1,k);
% [k,ind,prevind]
    segmentllh = llh(A(ind:prevind-1),ind,prevind-1); 
    totalllh = totalllh + segmentllh;
    boundaries(k) = ind;
    levels(k) = llhrepresentative(A(ind:prevind-1),ind,prevind-1);
    k = k-1;
end

function [res] = llh(B,aa,bb);

pp = llhrepresentative(B,aa,bb);
if pp==0||pp==1
   res=0;
else
   res = sum(B)*log2(pp)+(bb-aa+1 - sum(B))*log2(1-pp);
end

function [res] = llhrepresentative(B,aa,bb);

res = sum(B)/(bb-aa+1);
