function m = dynatrace(v)
% Recursive solution to max value of non-adjacent elements in 2 rows
% taking advantage of dynamic programming preservation of subproblem
% solutions, also trace back the path of the solution

% x represents the option we add nothing from column n
% y represents the option we add the top element from column n
% z represents the option we add the bottom element from column n

[r n] = size(v);
a = inf(3, n);                % 3 rows for 3 assumptions at pos n-1
a(1,1) = max([0; v(:,1)]);    % row 1:  Best if assume both at n-1 unused
a(2,1) = max([0; v(2,1)]);    % row 2:  Best if assume top at n-1 unused
a(3,1) = max([0; v(1,1)]);    % row 3:  Best if assume bottom at n-1 unused
t = zeros(3, n);              % trace back

m = f1(n);
a                             % display the subsolution array
t                             % display the trace back array

   % -------------------- Best if assume both at n-1 unused ------------
   function b = f1(n)
      if a(1,n-1) ~= inf         % Adding nothing at n best?
         x = a(1,n-1);           % Yippee, already computed
      else
         x = f1(n-1);            % Ok, we recurse
      end
      if a(2,n-1) ~= inf         % Adding top at n best?
         y = v(1,n)+a(2,n-1);    % Yippee, already computed
      else
         y = v(1,n)+f2(n-1);     % Ok, we recurse
      end
      if a(3,n-1) ~= inf         % Adding bottom at n best?
         z = v(2,n)+a(3,n-1);    % Yippee, already computed
      else
         z = v(2,n)+f3(n-1);     % Ok, we recurse
      end
      [b p] = max([x, y, z]);        % Find best of the 3 options x, y, z
      a(1,n) = b;                % Save subsolution
      t(1,n) = p;                % Keep track of path
   end

   % -------------------- Best if assume top at n-1 unused -----------
   function b = f2(n)
      if a(1,n-1) ~= inf         % Adding nothing at n best?
         x = a(1,n-1);
      else
         x = f1(n-1);
      end
      if a(3,n-1) ~= inf         % Adding bottom at n best?
         z = v(2,n)+a(3,n-1);
      else
         z = v(2,n)+f3(n-1);
      end
      [b p] = max([x, z]);
      a(2,n) = b;                % Save subsolution
      t(2,n) = p;
   end

   % -------------------- Best if assume bottom at n-1 unused --------
   function b = f3(n)
      if a(1,n-1) ~= inf         % Adding nothing at n best?
         x = a(1,n-1);
      else
         x = f1(n-1);
      end
      if a(2,n-1) ~= inf         % Adding top at n best?
         y = v(1,n)+a(2,n-1);
      else
         y = v(1,n)+f2(n-1);
      end
      [b p] = max([x, y]);
      a(3,n) = b;                % Save subsolution
      t(3,n) = p;
   end
end

