Code Chef RAINBOW Palindrome
(defn palindrome? [items]
  "Efficient algorithm: loops through only (array-size/2)"
     ...
         (not= (nth items i) 
               (nth items j))


nth is efficient on vectors and other things that support random indexing. On sequences, which you're passing in right now, it's O(n) per lookup since it has to walk the list.

Changing your test cases to use vectors should help (use mapv instead of map):

(let [...
      nums (mapv #(Integer/parseInt %) nums-temp)]




(def example (concat (range 1000) (reverse (range 1000))))
(count example)   ; 2000
(def examplev (vec example))
(count examplev)  ; 2000

(dotimes [_ 3] (time (palindrome? example)))
; "Elapsed time: 45.167334 msecs"
; "Elapsed time: 44.568282 msecs"
; "Elapsed time: 45.304136 msecs"

(dotimes [_ 3] (time (palindrome? examplev)))
; "Elapsed time: 0.317649 msecs"
; "Elapsed time: 0.272229 msecs"
; "Elapsed time: 0.30044 msecs"