Company: Tata digital_8aug
Difficulty: medium
Subsegment Sort Problem Description You have an array of n integers, arr[n] . Partition it into contiguous subsegments such that: Every element belongs to exactly one partition. After sorting each partition in non-decreasing order and concatenating all sorted partitions, resulting array matches the original array sorted in non-decreasing order. Your task is to find the maximum number of contiguous subsegments into which the array can be partitioned while maintaining this property. Complete the function findMaxSubsegmentsCount in the editor with the following parameter(s): int findMaxSubsegmentsCount(vector<int> arr) The function is expected to return an INTEGER . The function accepts INTEGER_ARRAY arr as parameter. Returns: int: the maximum number of contiguous subsegments in a valid set of partitions Examples Example 1: Input: n = 6, arr = [2, 5, 1, 9, 7, 6] Output: 2 Explanation: The original array sorted in non-decreasing order is [1, 2, 5, 6, 7, 9] . Try with 2 subsegments: S