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].

(iV) Answer = Max{(A[x]-A[u]),(A[v]-A[y])}

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
| cite | improve this answer | |
  • $\begingroup$ Yes. Can't it be better. $\endgroup$ – prithvi parre Oct 15 '17 at 18:22
  • $\begingroup$ Good question!!! Does not Kadane's algorithm give any idea? $\endgroup$ – fade2black Oct 15 '17 at 18:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.