You are given an array of N price changes for an item in some market. At each price change, you can buy the item, sell the item $($if you already have it$),$ or not do anything. Your goal is to make decisions that maximize your overall profit.

$012345$

Example. prices $=[1,3,2,8,4,9]$ Output $=12$

Explanation.

The maximum profit can be achieved by:

Buying at prices$[0]=-1$

Skipping prices$[1]$ and prices$[2]$

Selling at prices$[3]=+8$

Buying at prices$[4]=-4$

Selling at prices$[5]=+9$

The total profit is $-1+8-4+9=12.$

Design a backtracking algorithm to solve this problem. Follow the steps below:

A$.$ Draw a tree showing how a brute$-$force enumeration algorithm enumerates the candidate solutions for the following instance: prices $=[1,3,2]$

Clearly show on the tree what each node and edge represent. You don$$t have to draw the full tree as it might be large. However, you must show the root, the second level in the tree, and the full path to at least two feasible solutions and two infeasible solutions.

B$.$ Suggest a backtracking strategy to improve the running time of the brute$-$force algorithm.