Maximum Longest Increasing Subsequence
All submissions for this problem are available.
Given a sequence of integers, find the maximum difference between first and last element of the longest increasing subsequence.
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
For each test case print the maximum difference between first and last element of the longest increasing subsequence.
Input: 1 4 1 2 5 4 Output: 4 Explanation:(There are 2 Longest Increasing Subsequences:1 2 5 and 1 2 4. But the first subsequence gives the maximum difference(5-1=4)
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.