Maximum Longest Increasing Subsequence

Правка en2, от ironman7453, 2015-08-08 21:51:21

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

Теги dynamic programming, codechef

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский ironman7453 2015-08-08 22:03:01 11 Tiny change: 'ce in $O(n)$ time.\n\nProbl' -> 'ce in $O(n^2)$ time using dp.\n\nProbl'
en2 Английский ironman7453 2015-08-08 21:51:21 14
en1 Английский ironman7453 2015-08-08 21:50:56 686 Initial revision (published)