algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

thoughts.txt (959B)


      1 - starting with an array in non-decreasing order
      2     - a_1, a_2, ..., a_n
      3 - you can remove any number of elements from the array, including none, without changing the order of  the remaining elements
      4 - after all removals the following will happen:
      5     - a_1 is written to a new array
      6     - if a_1 + 1 < a_2 then a_2 is written to a new array, else a_2 is written to the same array as a_1
      7     - if a_2 + 1 < a_3 then a_3 is written to a new array, else a_3 is written to the same array as a_2
      8 - if a = [1,2,4,6], then
      9     - [1] 
     10     - since 1+1 !< 2
     11     - [1, 2]
     12     - since 2+1 < 4
     13     - [1, 2], [4]
     14     - since 4+1 < 6
     15     - [1, 2], [4], [6]
     16 
     17 -  Your task is to remove elements in such a way that the described algorithm creates as many arrays as possible. If you remove all elements from the array, no new arrays will be created.
     18 
     19 - idea:
     20     - do we just want to remove all elements until the delta between the last existing and the current is at least 2?