# How to maximize the profit

In CLRS , under the section "Maximum sub array problem", there is a problem to maximize the profit in the stock exchange. The problem is.. given an array A[1..n] and we have to find i and j such that i < j and A[j] - A[i] should be maximum. the solution given is O(n^2) . But I have a solution which does it in O(n) . I know it should be wrong , But I cant find a single counter example to my solution.

My solution :

(i) Find the maximun and minimum in A[1..n] . Let A[x] be the maximum and A[y] be the minimum.

(ii) And find minimum in A[1..x] . Let that be A[u].

(iii)Find maximum in A[y..n] . Let that be A[v].

What am I doing wrong?

### Counter example

Consider the array $A=[5,2,3,4,1]$, where $n=5$.

(i) Then $A[1]=5$ is the maximum and $x=1$, $A[5]=1$ is the minimum and $y=5$.

(ii) And find minimum in $A[1 .. x] = A[1 .. 1]=A[1]$ which is $5$. So, $u=1$.

(iii) Find maximum in $A[y..n] = A[5..5]= A[5]$ which is $1$. So, $v=5$.

(iv) Answer is $$\max(A[x]-A[u]),(A[v]-A[y]) = \max(A[1]-A[1], A[5]- A[5])= \max(0,0)=0$$

But the maximum profit is $A[4] - A[2] = 2$.

### $O(n)$ solution

The idea is to start with two pointers $i=1$ and $j=2$ and at each step increase $j$ by one. At each step check if the difference $A[j] - A[j]$ is greater than the maximum profit. If it is then update the maximum profit. But if $A[i] > A[j]$ (in which case $A[j] - A[j]$ is negative and max profit is not updated) then we make $i$ point to the same location $j$ points to, since if for some $k > j$, $A[k] - A[i]$ is greater than the current maximum profit then $A[k] - A[j] > A[k] - A[i] > maxprofit$.

1. Set $i=1$, $j=2$, $maxprofit=0$
2. If $A[j] - A[i] > maxprofit$ then set $maxprofit = A[j] - A[i]$
3. If $A[i] > A[j]$ then set $i = j$
4. $j = j + 1$
5. If $j>n$ return $maxprofit$
6. Goto 2
• Yes. Can't it be better. – prithvi parre Oct 15 '17 at 18:22
• Good question!!! Does not Kadane's algorithm give any idea? – fade2black Oct 15 '17 at 18:52