Suppose we have a rod of length n inches and we also have an array of positive integer prices P$,$ where$$P$[$i$]$ denotes the selling price $($$$)$ of a piece that is i inches long. Suppose now we have to pay a cost of$$$$1$ per cut. You are only allowed to cut the rod into $($positive$)$ integer sized pieces. Define the profit we$$make as the revenue $($sum of prices of the pieces$)$ minus the total cost of cutting. We want an algorithm$$that finds a way to cut the rod maximizing our profit. For your DP algorithm, use the name MaxProfit$$for the array which stores values of the subproblems.$1.$ Subproblems: Define appropriate subproblems MaxProfit in words. You should explain what the$$entries in MaxProfit are intended to store.$2.$ Base Cases: State the base case$($s$)$ and their value$($s$).3.$ Recurrence: State and justify the recurrence MaxProfit should satisfy.$4.$ Algorithm: Based on the recurrence, write pseudocode that computes MaxProfit and outputs the$$maximum profit for the given rod of length n$.5.$ Run$-$Time: State and justify the run time of your algorithm as a $\backslash$Theta expression.