Let 𝐴 be an array containing integer values. The distance of 𝐴 is defined as the minimum number of…

Question

Let 𝐴 be an array containing integer values. The distance of 𝐴 is defined as the minimum number of elements in 𝐴 that must be replaced with another integer so that the resulting array is sorted in non-decreasing order. The distance of the array [2, 5, 3, 1, 4, 2, 6] is ___________

Accepted Answer

Correct answer: 3 — Key idea: the minimum number of replacements equals the array length minus the length of the longest non-decreasing subsequence (LNDS). Find a longest non-decreasing subsequence. For [2, 5, 3, 1, 4, 2, 6], one LNDS is 2, 3, 4, 6 (indices 1, 3, 5, 7), so its length is 4. Compute replacements needed = total elements (7) − LNDS length (4) = 3. Therefore the distance of the array is 3.

Let 𝐴 be an array containing integer values. The distance of 𝐴 is defined as…