I am trying to solve this problem, but so far no luck. Can anybody show me the correct approach. I know that it is possible to find longest increasing subsequence in O(n) time.

Problem statement: Given a sequence of integers, find the maximum difference between first and last element of the longest increasing subsequence. Input: First line contains T, number of test cases followed by T test cases. For each test case first line contains an integer N , the next line contains sequence of N integers. Constraints: T <  = 100 1 <  = N <  = 10000 All numbers in the sequence will fit into 64-bit integer