 # Sub and super array

Problem: Given an distinct array, find two increasing subarrays(say `a` and `b` ) such that when joined they produce one increasing array(say `ab` ). We need to find max possible length of array `ab`.
The subarray should be contiguous.
The two subarray should not overlap

For example: given `array = [7 2 5 8 6 3 9 10]`

Two sub arrays are `a = [2 5 8]` , `b = [9, 10]` and `ab = [2 5 8 9 10]` Output: `length(ab) = 5`

3 is not included in b because it is overlapping the subarray ‘a’.

1 Like

Plz share the problem link as it can be of some ongoing contest…

This not an contest problem actually it was asked me two days before in a online coding interview i got stuck in this problem and i am not able to crack it, if you know please help me out, anyway that interview was over.

Find the next greater element for each element using a stack. Then sweep through the array to find an increasing block. After that find a corresponding second block.

Code
Next Greater Element
``````stack<int> s;
vector<int> nextGreater(n, n);
for(int i = 0; i < n; i++) {
while(s.size() and A[s.top()] < A[i]) {
nextGreater[s.top()] = i;
s.pop();
}
s.push(i);
}
``````
``````int i = 0, ans = 0;
while(i < n) {
int cur = A[i], firstBlock = 1; i++;
while(i < n and cur < A[i]) {
cur = A[i];
i++;
firstBlock++;
}
if(i == n) {
// we can break this first block into two blocks
ans = max(ans, firstBlock);
// nothing more to search
break;
}
int j = nextGreater[i - 1];
if(j == n) continue; // cannot find second block
cur = A[j]; j++;
int secondBlock = 1;
while(j < n and cur < A[j]) {
cur = A[j];
j++;
secondBlock++;
}
ans = max(ans, firstBlock + secondBlock);
}
cout << ans << "\n";
``````

Can be optimised by preprocessing the longest increasing block that starts at index j.

[EDIT] This approach is wrong.

2 Likes

It is solvable using Dynamic Programming. Just output the length of the Longest Common Subsequence of 2 arrays, i.e. one which is given (here [7 2 5 8 6 3 9 10]) and one which is sorted one of the given array (here [2 3 5 6 7 8 9 10]).

1 Like

This might not give two contiguous blocks. What you are suggesting is essentially finding the longest increasing subsequence, which is something different.

For finding LIS, this method takes O(n^2). There is another method with O(n\log n), but it is not useful here.

Your algo will fail on this:
6
4 8 3 7 9 10
Your code gives output 5 but I don’t think you can form ‘ab’ of length 5

Proceed like this(assuming 1-based indexing):

``````Define dp1[i] = maximum increasing subarray ending at 'i'
dp2[i] maximum increasing subarray starting at index 'i'
dp1 = 1, dp2[n] = 1
dp1[i] = dp1[i-1] + 1, if arr[i] > arr[i-1], else 1
dp2[i] = 1 + dp2[i+1], if arr[i] < arr[i+1], else 1
ans = 0
for i = 1 to n
for every element 'j' in (i+1, n) such that a[j] > a[i]
ans = max(ans, dp1[i] + dp2[j])
return ans
``````

This can be optimized to O(n*log(n)) using segment trees

3 Likes

My bad. That should be `int j = nextGreater[i - 1]`, for which it outputs `4`. Is my logic not right?

1 Like

Actually it is similar to LIS but they gave two condition we have to select two subarray which is strictly increasing and two subarray should not overlap in terms of range(one array should not contain a number between highest and lowest number of another array). we have to merge two arrays that should result an strictly increasing array and also an longest array.

Try on this:
7
2 6 3 4 7 9 10

Output: `5`
`[3, 4, 7] [9, 10]`

My logic is the same as yours. I have just not memorized the values in `dp[]`, as the overall complexity turns out to be O(n^2) anyways.

1 Like

Output should be 6, your code outputs 5
 , [3, 4 ,7, 9, 10]
The fault in you algo is that cannot take complete full subarray, let’s say the 2 increasing subarrays are [i, j] and [k, l] with j < k, then you need to chose ‘x’ and ‘y’ such that ab = [i, x] + [y, l], x <= j, y >= k and a[x] < a[y] with len(ab) maximized

1 Like

Thank you Thanks! My code tries to greedily increase the length of the first block. Which is why it fails. I’ll have to compute an answer each time I try to extend my first block.

1 Like

Can you please tell how to apply segment tree?

First compress the values so that all a[i] are in range [1, n]. This won’t change our answer since we are concerned with relative order among elements only. Once we have built both dp1 and dp2, start iterating from back of the array. We would build a max segment tree. Now you need to update the node corresponding to value a[i] with dp2[i].
To find the value of ans, you need to search for maximum value in range [a[i] + 1, maxn], where maxn is the maximum node you have used in segment tree and add it to dp1[i]. Note that since elements [i, n] have only been inserted in segment tree, the maximum value that you would get corresponds to maximum dp2[j] in the pseudo-code above.

1 Like

Thank You!