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’.
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.
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.
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]).
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] = 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
My bad. That should be int j = nextGreater[i - 1], for which it outputs 4. Is my logic not right?
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.
Output should be 6, your code outputs 5
[2] , [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
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.
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.
Thank You!