Create Lexicographically Greatest Array

The resulting array may have ‘i’ elements from ‘arr1’ and ‘K’ - ‘i’ elements from ‘arr2’, where ‘i’ can be any integer from ‘0’ to min(‘K’, size of ‘arr1’). So we can iterate through all these ‘i’ and find a resultant array which is lexicographically maximum. First thing to observe is that if we choose a subsequence ‘X’ of length ‘K1’ from ‘arr1’ and subsequence ‘Y’ of length ‘K2’ form ‘arr2’ such that ‘K1’ + ‘K2’ = ‘K’, and after merging ‘X’ and ‘Y’ we will get a array say ‘result’ that is lexicographically maximum, then ‘X’ and ‘Y’ must be lexicographically maximum possible also. For example let ‘X be [ ‘x1’, ‘x2’]  and ‘Y’ be [ ‘y1’, ‘y2’ ] and ‘result’ be [ ‘ x1’ , ‘y1’, ‘x2’, ‘y2’], Now we say that the ‘result’ is lexicographically maximum, and let there exists another subsequence in ‘arr1’ of length 2 such that it is lexicographically greater than ‘X’ but then ‘result’ cannot be lexicographically maximum.

So now, the problem can be divided into two parts.

1. Finding lexicographically maximum subsequences from ‘arr1’ for each length ‘X’, and  lexicographically maximum subsequences from ‘arr2’ of length ‘K’ - ‘X’, where ‘X’ is from 0 to length of ‘arr1’
2. Merging two subsequences in a way to obtain a lexicographically maximum array.

To find lexicographically maximum subsequences from an array, we can use stack. We will maintain a non-increasing stack of size of ‘K’ elements. We iterate over the array and pop the elements in the stack until the current element is greater than the top element in the stack and push the current element. 

For example, let the array be [ 6, 8, 5, 4, 2, 6, 6, 10 ] and we need a subsequence of size 3.

• We start with pushing ‘6’ into the stack, stack: [ 6 ]
• 8 is greater than 6 so we pop 6 from the stack and push 8, stack: [ 8 ]
• 5 is less than 8, so push 5, stack : [ 8, 5 ].
• 4 is less than 5, so push 4, stack : [ 8, 5, 4 ]
• 2 is less than 4, but stack size is already 3 so we don’t push anymore.
• 6 is greater than 4 and 5 so pop both and push 6, stack : [ 8, 6 ]
• 6 is equal to 6, so we will push 6, stack: [ 8, 6, 6 ]
• 10 is greater than 6 but we now only pop one 6 because popping second 6 cannot make a subsequence with size 3. As 10 is the last element in the array. So the final stack becomes [8, 6, 10].

To merge two subsequences such that we obtain a lexicographically maximum array, we just use the merge technique as done in merge sort, with a slight modification i.e to add each element into a merged array we not only check the current element from both arrays, we have to check subarrays of both arrays starting from the current element to the length of the arrays, and then we add the element of an array whose subarray is lexicographically greater. For example, if the arrays are [2, 2, 4] and [2, 2, 2, 5]. For the first element of the merged array, we don’t check only the first element of both arrays as done in merge sort, here we have to check subarrays of both arrays starting from index 0 to length of both arrays i.e [2, 2, 4] and [2, 2, 2, 5]. And we can see that the first array is lexicographically bigger. So we add ‘2’ of the first array into ‘merged’.

Algorithm:

• Let ‘arr1’ and ‘arr2’ be the given first and second array with length ‘N’ and ‘M’.
• Declare a function say ‘getSeq’ to find the lexicographically maximum subsequence of size ‘x’ in an array.
• Declare a function say ‘isGreater’ to find a lexicographically greater array from the given two arrays.
• Declare a function say ‘merge’ to merge two sequences into one array.
• Declare an empty array say ‘result’ to store the resultant array.
• Run a loop from i = 0 to min (‘K’ , ‘N’ )
  • If ‘K’ - ‘i’  < ‘M’, which means we can take a subsequence of size ‘i’ from ‘arr1’ and subsequence of size ‘K’ - ‘i’ from ‘arr2’.
    • Find the lexicographically maximum subsequence of size ‘i’ in ‘arr1’ by calling the function ‘getSeq’ and store this array in ‘seq1’.
    • Find the lexicographically maximum subsequence of size ‘K’ - ‘i’ in ‘arr2’ by calling the function ‘getSeq’ and store this array in ‘seq2’.
    • Call merge(‘seq1’, ‘seq2’) and store the returned array in ‘temp’.
    • If ‘temp’ array is lexicographically greater than ‘result’
      • Then update the ‘result’ array to temp.

Description of ‘isGreater’ function

The Function compares two arrays for lexicographic order, it will return true if the subarray ‘firstArr[ ‘idx1’ : size of ‘firstArr’ ]’ is lexicographically bigger than ‘secArr [ ‘idx2’ : size of ‘secArr’ ]’ .  

The function will take two parameters:

• ‘firstArr’: first array
• ‘secArr’: second array.
• ‘idx1’: start index of first array to compare
• ‘idx2’: start index of second array to compare.

bool isGreater ( ‘firstArr’, ‘secArr’, ‘idx1’, ‘idx2’ ):

• Run a while loop until ‘idx1’ is less than the size of ‘firstArr’ and  ‘idx2’ is less than size of ‘secArr’  and ‘firstArr[idx]’ == ‘secArr[i]’.
  • Increment ‘idx1’ and ‘idx2’ by 1. I.e ‘idx1’ += 1, ‘idx2’ += 1.
• If ‘idx2’ == ‘secArr’, that means all the elements of ‘secArr’ form initial ‘idx2’ to size of ‘secArr’ are equal to elements of ‘firstArr’ from initial ‘idx1’ to size of ‘secArr’. So either ‘firstArr’ will be greater than ‘secArr’ or equal
  • Return true.
• If ‘idx1’ < size of ‘firstArr’  and ‘firstArr[idx1]’ > ‘secArr[idx2]’
  • Return true, as the ‘first’  array is greater than ‘secArr’.
• Return false as ‘secArr’ is greater than ‘firstArr’.

Description of ‘getSeq’ function

This function will return the lexicographically maximum possible subsequence of length ‘len’ from ‘arr’. 

The function will take two parameters:

• ‘arr’: array to get subsequence
• ‘len’: length of subsequence required.

array getSeq ( ‘arr’, ‘len’ ):

• Declare a stack to find lexicographically max subsequence.
• Run a loop from i = 0  to size of ‘arr’ - 1.
  • Run a while loop until the stack is not empty and top element of the stack is less than arr[i] and size of stack + remaining elements in ‘arr’ is not less than ‘len’
    • Pop an element from the stack.
• Return the elements of the stack in reverse order.

Description of ‘merge’ function

This function will merge two given arrays such that the merged array is lexicographically maximum.

The function will take two parameters:

• ‘firstArr’: the first array
• ‘secArr’: the second array.

array merge ( ‘firstArr’, ‘secArr’, ‘idx1’, ‘idx2’ ):

• Declare an empty array say ‘merged’ to store the merged array.
• Declare two variables say ‘idx1’ and ‘idx2’ to keep track of current elements on both given arrays.
• Run a loop until ‘idx1’ is less than the size of ‘firstArr’ or ‘idx2’ is less than the size of ‘secArr’
  • The subarray of ‘firstArr’ from ‘idx1’ to length of ‘firstArr’ is lexicographically greater than the subarray of ‘secArr’ from ‘idx2’ to length of ‘secArr’.
    • Add the element of ‘firstArr’ into ‘merged’ i.e ‘firstArr[idx1]’.
    • Increment ‘idx1’ by 1.
  • Else, add the element of ‘secArr’ into ‘merged’ i.e. ‘secArr[idx2]’ and increment ‘idx2’ by 1.
• Return ‘merged’.

In the previous approach, we are using the ‘getSeq’ function to get a lexicographically maximum subsequence of a given size. Another way to find a max lexicographically subsequence of size say ‘i’ can be done using the lexicographically maximum subsequence of size  ‘i +1’. Let say the array is of size ‘N’ then lexicographically maximum subsequence of size  ‘N’ will be the array itself, now to find a lexicographically maximum subsequence of size  ‘N - 1’ we need to delete an element from the first subsequence, and “we can observe that we will delete the first element that is smaller than its next element in the previous subsequence”. 

For example let the previous subsequence of length 4 be [ 3, 4, 2, 5], we can get the next lexicographically maximum subsequence with length 3 by deleting 2, as this is the first element that is less than its next element (5). And if the previous subsequence is non -increasing, then we can simply delete the last element to get the next lexicographically maximum subsequence.

For example let the array be [6, 8, 2, 6, 5, 3].

• The lexicographically maximum subsequence of size 6 will be array itself i.e [6, 8, 2, 6, 5, 3]
• The next sequence of size 5 will be obtained by deleting 6 from the previous sequence, now seq: [8, 2, 6, 5, 3 ].
• The next sequence of size 4 will be obtained by deleting 2 from the previous sequence, now seq: [8, 6, 5, 3 ].
• The next sequence of size 3 will be obtained by deleting 3 from the previous sequence, as all elements are non -increasing so now seq: [8, 6, 5 ].
   

Repeat above for all sizes of subsequence.

So we use two 2-D arrays ‘dp1’ and ‘dp2’ where ‘dp1[i]’ is the lexicographically maximum subsequence of size ‘i’ from ‘arr1’, And dp2[i]’ is the lexicographically maximum subsequence of size ‘i’ from ‘arr2’. We can calculate ‘dp[i]’ from ‘dp[i + 1]’ as above, and ‘dp1[n]’ = ‘arr1’ and ‘dp2[n]’ = ‘arr2’.

Algorithm:

• Let ‘arr1’ and ‘arr2’ be the given first and second array with lengths ‘N’ and ‘M’.
• Declare two 2-D arrays say ‘dp1’ and ‘dp2’ to store lexicographically maximum subsequence of each size from 0 to length of given arrays.
• Declare a function say ‘storeDp’ to find the lexicographically maximum subsequence of size each size from 0 to size of passed array.
• Declare a function say ‘isGreater’ to find a lexicographically greater array from the given two arrays.
• Declare a function say ‘merge’ to merge two sequences into one array.
• Declare an empty array say ‘result’ to store the resultant array.
• Call ‘storeDp’ for ‘arr1’.
• Call ‘storeDp’ for ‘arr2’.
• Run a loop from i = 0 to min (‘K’ , ‘N’ )
  • If ‘K’ - ‘i’  < ‘M’, which means we can take a subsequence of size ‘i’ from ‘arr1’ and subsequence of size ‘K’ - ‘i’ from ‘arr2’.
    • Call merge(‘dp1[ i ]’, ‘dp2[ K - i ]’) and store the returned array in ‘temp’.
    • If ‘temp’ array is lexicographically greater than ‘result’
      • Then update the ‘result’ array to temp.
• Return result.

Description of ‘storeDp’ function

The function will take two parameters:

• ‘arr’: array to get subsequence
• ‘dp’: 2-D array to store subsequences of all sizes.

void storeDp ( ‘arr’, ‘dp’ ):

• Declare a variable say ‘pointer’ to keep track of the current position in the previous subsequence and initialize it with 0.
• Run a loop from i = 0 to size of ‘arr’.
  • dp[ ‘arr.size’ ] = ‘arr’.
  • Increment ‘pointer’  by 1 until  ‘pointer’ < size of ‘arr’ -1 and ‘arr[ pointer ]’ >= ‘arr[ pointer + 1]’.
  • Erase element at ‘pointer’ in ‘arr’.
  • If ‘pointer’ is non-zero.
    • Decrement ‘pointer’ by 1.