Sub and super arrays
Practice
5 (1 votes)
Advanced data structures
Data structures
Lazy propagation in interval/segment trees
Medium
Segment tree
Problem
48% Success 414 Attempts 30 Points 1.5s Time Limit 256MB Memory 1024 KB Max Code

You are given an array \(Arr_i\) of size \(N\) containing distinct integers. You have to choose two non-overlapping subarrays and join them to make a super array such that all elements in the super array are strictly in increasing order. Find the maximum size of the super array.

For example, if the given array is \(Arr[1,2.....i....j.....x...y....N]\) and you choose subarrays \([i....j]\) and \([x....y]\) to form the super array, then the super array will be \([i....j,x...y]\) where (\(1 \le i \le j \lt x \le y \le N\)).

Notes

  • The swapping of elements is not allowed.
  • The subarray in the final optimal answer will always contain distinct numbers.
  • It is always possible to choose 2 subarrays that follow the given criteria.

Input format

  • First line: \(T\) i.e number of test cases.
  • For each test case:
    • First line: \(N\)
    • Second line: \(N\) space-separated integers denoting elements of the array

Output format
Find the maximum size of the super array. Print the answer to each test case in a separate line.

Constraints
\(1 \le T \le 20\)
\(1 \le N,Arr_i \le 100000\)

 

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:20
18 votes
Tags:
ApprovedEasyImplementationMathOpen
Points:20
18 votes
Tags:
Hash tableData StructuresEasyOpenApprovedHash function
Points:20
77 votes
Tags:
ApprovedBasic ProgrammingEasyImplementationOpen