- 2

# Minimum array edit Algorithm

[challenge] Given the integer array a = [A1, A2, ···, an]. Your task is to do a series of operations on the array to make it non descending Group: in each operation, you need to select a number x, and then move all elements equal to X in the array to the beginning or end of the array Tail. For example, array a = [2, 1, 3, 1, 1, 3, 2] can be changed into a non descending array by the following two operations: 1. Move all elements equal to 1 to the beginning of the array to get [1, 1, 1, 2, 3, 3, 2] ; 2. Move all elements equal to 3 to the end of the array to get [1, 1, 1, 2, 2, 3, 3]. design an algorithm to calculate the minimum number of operations required to change a given array into a non descending array.

1 Answer

+ 1

The question is equivalent to finding the longest increasing chain of elements b1 < b2 <... <bm such that for each k, the last occurence of bk in a happens before the first occurence of b(k+1).

Hot today

How to read this?

1 Votes

Class and instance attributes

1 Votes

How does this works?

1 Votes

Please help

1 Votes

Button after Button

0 Votes

FYP PROJECT IDEAS

0 Votes