91影视

Let us suppose$P\left(i\right)$be the maximum profit Yuckdonald can fetch from restaurants that are open in location from 1 to i.

So if$i=0$, this implies that there is no location available to open a restaurant.

Thus$P\left(0\right)=0$i.e., Profit is 0 as no restaurant is open.

So based on our constraints we will define a recursion relation,

$\mathit{P}\mathbf{\left(}\mathit{i}\mathbf{\right)}\mathbf{=}\mathit{M}\mathit{A}\mathit{X}\{\begin{array}{l}\left(MA{X}_{i<j}\right(P\left(j\right)+尾(m_i,m_j).p_i)\\ p_i\end{array}$

Here,

role="math" localid="1657267434540" $\mathbf{P}\mathbf{\left(}\mathbf{j}\mathbf{\right)}\mathbf{=}\mathbf{}\mathit{M}\mathit{a}\mathit{x}\mathit{i}\mathit{m}\mathit{u}\mathit{m}\mathbf{}\mathit{p}\mathit{r}\mathit{o}\mathit{f}\mathit{i}\mathit{t}\mathbf{}\mathit{o}\mathit{b}\mathit{t}\mathit{a}\mathit{i}\mathit{n}\mathbf{}\mathit{f}\mathit{r}\mathit{o}\mathit{m}\mathbf{}\mathit{l}\mathit{o}\mathit{c}\mathit{a}\mathit{t}\mathit{i}\mathit{o}\mathit{n}\mathbf{}\mathbf{鈥�}\mathbf{j}\mathbf{鈥�}\mathbf{}$

But if profit obtain from location 鈥榠鈥� is more then location 鈥榡鈥� or if it鈥檚 not possible to locate restaurant at location 鈥榡鈥�, then 鈥�$p_i$鈥� will be our maximum profit.

Here, symbol $尾$will define whether there can be a restaurant at location i .

So we define$尾$as:

$\mathbf{尾}\mathbf{=}\{\begin{array}{l}0;\mathrm{if}(m_i-m_j)<k\\ 1;\mathrm{if}(m_i-m_j)>k\end{array}$

We will initiate an array$Profit[]$that will tell about expected profit from location 鈥榠鈥�

Here, v variable will store temporary value of$Profit\left[i\right]$ .

$$\begin{gathered} fori=1toN \\ Profit\left[i\right]=0 \\ fori=2toN \\ forj=1toi-1 \\ v=\left(Profit\right[j]+尾(mi,mj).P[i\left]\right) \\ ifv>Profit\left[i\right] \\ v=Profit\left[i\right] \\ ifProfit\left[i\right]<P\left[i\right] \\ Profit\left[i\right]=P\left[i\right] \end{gathered}$$

Since two loops are executing here, so collectively the time complexity is $O\left(n^2\right)$.