Efficient code in Java please

Read the entire input one line at a time and then output a subsequence of the lines that appear in the same order they do in the file and that are also in non-decreasing or non-increasing sorted order. If the file contains n lines, then the length of this subsequence should be at least sqrt(n). For example, if the input contains 9 lines with the numbers 2, 1, 3, 7, 4, 6, 9, 5, 8 then your output should have at least 3 lines, which could be 1,3,4 (increasing) or 2,3,7 (increasing) or 1,4,6,9 (increasing) or 2,6,8 (increasing) or 7,6,5 (decreasing) or ...). Warning/Hint: This is probably the hardest question. You're being asked to implement the ErdsSzekeres theorem