title: Find longest quasi-constant sub-sequence of a sequence
body: <p>I had this test earlier today, and I tried to be too clever and hit a road block. Unfortunately I got stuck in this mental rut and wasted too much time, failing this portion of the test. I solved it afterward, but maybe y'all can help me get out of the initial rut I was in.</p>
  
  <p><strong>Problem definition:</strong></p>
  
  <p><em>An unordered and non-unique sequence A consisting of N integers (all positive) is given. A subsequence of A is any sequence obtained by removing none, some or all elements from A. The amplitude of a sequence is the difference between the largest and the smallest element in this sequence. The amplitude of the empty subsequence is assumed to be 0.</em></p>
  
  <p><em>For example, consider the sequence A consisting of six elements such that:</em></p>
  
  <pre><code>A[0] = 1
  A[1] = 7
  A[2] = 6
  A[3] = 2
  A[4] = 6
  A[5] = 4
  </code></pre>
  
  <p><em>A subsequence of array A is called quasi-constant if its amplitude does not exceed 1. In the example above, the subsequences [1,2], [6,6], and [6,6,7] are quasi-constant. Subsequence [6, 6, 7] is the longest possible quasi-constant subsequence of A.</em></p>
  
  <p><em>Now, find a solution that, given a non-empty zero-indexed array A consisting of N integers, returns the length of the longest quasi-constant subsequence of array A. For example, given sequence A outlined above, the function should return 3, as explained.</em></p>
  
  <p>Now, I solved this in python 3.6 after the fact using a sort-based method with no classes (my code is below), but I didn't initially want to do that as sorting on large lists can be very slow. It seemed this should have a relatively simple formulation as a breadth-first tree-based class, but I couldn't get it right. Any thoughts on this?</p>
  
  <p><strong>My class-less sort-based solution:</strong></p>
  
  <pre><code>def amp(sub_list):
      if len(sub_list) &lt;2:
          return 0
      else:
          return max(sub_list) - min(sub_list)
  
  def solution(A):
      A.sort()
      longest = 0
      idxStart = 0
      idxEnd = idxStart + 1
      while idxEnd &lt;= len(A):
          tmp = A[idxStart:idxEnd]
          if amp(tmp) &lt; 2:
              idxEnd += 1
              if len(tmp) &gt; longest:
                  longest = len(tmp)
          else:
              idxStart = idxEnd
              idxEnd = idxStart + 1
      return longest
  </code></pre>