GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

Sunday, 22 May 2022

[Solution] LIS or Reverse LIS? Codeforces Solution | Codeforces Problem Solution 2022

C. LIS or Reverse LIS?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array a of n positive integers.

Let LIS(a) denote the length of longest strictly increasing subsequence of a. For example,

  • LIS([2,1_,1,3_]) = 2.
  • LIS([3_,5_,10_,20_]) = 4.
  • LIS([3,1_,2_,4_]) = 3.

We define array a as the array obtained after reversing the array a i.e. a=[an,an1,,a1].

The beauty of array a is defined as min(LIS(a),LIS(a)).

Solution Click Below:-  CLICK HERE

Input

The input consists of multiple test cases. The first line contains a single integer t (1t104)  — the number of test cases. Description of the test cases follows.

The first line of each test case contains a single integer n (1n2105)  — the length of array a.

The second line of each test case contains n integers a1,a2,,an (1ai109)  — the elements of the array a.

It is guaranteed that the sum of n over all test cases does not exceed 2105.

Output

For each test case, output a single integer  — the maximum possible beauty of a after rearranging its elements arbitrarily.

No comments:

Post a Comment