AMAZON Coding Question – Solved

Amazon Games has recently launched a new game called Match the Column in which players are supposed to match the numbers from the left column to the right column like a traditional match the column game. Given an array of integers, match, the i-th index in the left column is matched with match[i] in the right column. There is a twist: Intersecting matches, illustrated below, are not allowed. Determine the maximum number of matches possible without any intersections. In the left illustration, match = [4, 3, 2, 3, 5]. More formally, two matches (i, match[i]) and (j, match[j]) intersect if i < j and match[i] > match[j] or i > j and match[i] ≤ match[j]. Example: Given n = 4, match = [2, 2, 1, 3]. There cannot be more than 2 valid matches, as shown above. Note that both illustrations are optimal. Return 2. Function Description: Complete the function getMaxMatching in the editor below. getMaxMatching has the following parameter: int match[n]: an array of integers Returns: int: the maximum number of matchings possible Constraints: - 1 ≤ n ≤ 10^5 - 1 ≤ match[i] ≤ n Input Format For Custom Testing: Sample Case 0 Sample Input For Custom Testing: STDIN 6 3 1 4 2 3 5 Function match[] size n = 6 match = [3, 1, 4, 2, 3, 5] Sample Output: 4 Explanation: Given n = 6, match = [3, 1, 4, 2, 3, 5], the matchings are (1, 3), (2, 1), (3, 4), (4, 2), (5, 3), (6, 5). It is optimal to match (2, 1), (4, 2), (5, 3), (6, 5), none of which intersect.