3 sequential numbers

Alright geniuses, if you think your programming ability is up to par, lets see you solve this:

Write an algorithm which in O(n) time finds 3 indices i, j, and k such that i < j < k and array[i] < array[j] < array[k].

>>61

there is nothing maintaining that i < j < k.


(define (for-range-fn low high parameterized-body)
  (if (< low high)
    (begin (parameterized-body low)
           (for-range-fn (+ low 1) high parameterized-body))))

(define (blah array)
  (define min 999999999999)
  (define max 0)
  (define min+1 999999999999)
  (define i #f)
  (define j #f)
  (define k #f)
  (for-range-fn 0 (vector-length array) (lambda (x)
    (define current (vector-ref array x))
    (cond
      ((< current min)
       (display `(min goes from ,min to ,current)) (newline)
       (set! min current)
       (set! i x))
      ((and (> current min) (< current min+1))
       (display `(min+1 goes from ,min+1 to ,current)) (newline)
       (set! min+1 current)
       (set! j x))
      ((> current max)
       (display `(max goes from ,max to ,current)) (newline)
       (set! max current)
       (set! k x)))))
  (values i j k))


(blah (vector 999 1 998 1 1000 7 2 8 3 8  2 9 3 4 10 4 5 6))


(min goes from 999999999999 to 999)
(min goes from 999 to 1)
(min+1 goes from 999999999999 to 998)
(max goes from 0 to 1)
(max goes from 1 to 1000)
(min+1 goes from 998 to 7)
(min+1 goes from 7 to 2)
 1
 6
 4

good try though. I'm sure something similar to this could work.