title: Javascript Codility Maximum Slice problem
body: <p>Im attempting the following algorithm problem in Javascript from Codility:</p>
  
  <p>An array A consisting of N integers is given.<br>
  It contains daily prices of a stock share for a period of N consecutive days.<br>
  If a single share was bought on day <strong>P</strong> and sold on day <strong>Q</strong>,<br>
   where <code>0 ≤ P ≤ Q &lt; N</code>,<br>
  then the profit of such transaction is equal to <code>A[Q] − A[P]</code>,<br>
  provided that <code>A[Q] ≥ A[P]</code>.  </p>
  
  <p>Otherwise, the transaction brings loss of <code>A[P] − A[Q]</code>.  </p>
  
  <p>For example, consider the following array A consisting of six elements such that:</p>
  
  <pre><code>  A[0] = 23171
    A[1] = 21011
    A[2] = 21123
    A[3] = 21366
    A[4] = 21013
    A[5] = 21367
  </code></pre>
  
  <p>If a share was bought on day 0 and sold on day 2, a loss of <code>2048</code> would occur because <code>A[2] − A[0] = 21123 − 23171 = −2048</code>.<br>
  If a share was bought on day 4 and sold on day 5, a profit of <code>354</code> would occur because <code>A[5] − A[4] = 21367 − 21013 = 354</code>.<br>
  Maximum possible profit was <code>356</code>.<br>
  It would occur if a share was bought on day 1 and sold on day 5.  </p>
  
  <p>Write a function,</p>
  
  <p>function solution(A);</p>
  
  <p>that, given an array A consisting of N integers containing daily prices of a stock share for a period of N consecutive days, returns the maximum possible profit from one transaction during this period.<br>
  The function should return 0 if it was impossible to gain any profit.</p>
  
  <p>For example, given array A consisting of six elements such that:</p>
  
  <pre><code>  A[0] = 23171
    A[1] = 21011
    A[2] = 21123
    A[3] = 21366
    A[4] = 21013
    A[5] = 21367
  </code></pre>
  
  <p>the function should return <code>356</code>, as explained above.</p>
  
  <p>Write an efficient algorithm for the following assumptions:</p>
  
  <p><code>N</code> is an integer within the range <code>[0..400,000]</code>;
  each element of <code>array A</code> is an integer within the range <code>[0..200,000]</code>.</p>
  
  <p>This is my current solution, it fails on performance on 'chaotic sequence of 200K values from [100K..120K], then 200K values from [0..100K]' where it succeeds 0.07 seconds too late.  </p>
  
  <pre><code>function solution(A) {
      length = A.length
      if (A &gt; 400000) return 0
      let lastStart = A[0]
      let lastMax = A[0]
      let diff = 0
      for (i=0; i &lt; length; i++){
          if (A[i] &lt; lastMax) lastMax = A[i]
          if (A[i] &lt; lastStart) lastStart = A[i]
          if (A[i] &gt; lastMax) {
              lastMax = A[i]
              if (lastMax - lastStart &gt; diff) diff = lastMax - lastStart
          }
      }
      return diff &gt; 0 ? diff : 0
  }
  </code></pre>
  
  <p>This appears to be O(N) and so should pass but seems to be failing.<br>
  Can anyone see what is causing this.<br>
  I know there are other ways to solve this problem but I really want to know why this method is failing the time limit.</p>
  
  <p>Thanks!</p>