Dado un arreglo A, podemos realizar una inversión de panqueque: seleccionamos un entero positivo k ≤ A.length e invertimos el orden de los primeros k elementos. Debemos realizar cero o más inversiones (una tras otra) para ordenar el arreglo A.

El objetivo es devolver una secuencia de valores k que representen las inversiones realizadas, que al aplicarse en orden, resulten en un arreglo ordenado. Cualquier respuesta válida con un número de inversiones menor o igual a 10 * A.length será aceptada.

Ejemplo 1:

Entrada: [3,2,4,1]
Salida: [4,2,4,3]
Explicación:
Realizamos 4 inversiones con k = 4, 2, 4, 3.
Estado inicial: [3, 2, 4, 1]
Tras inversión (k=4): [1, 4, 2, 3]
Tras inversión (k=2): [4, 1, 2, 3]
Tras inversión (k=4): [3, 2, 1, 4]
Tras inversión (k=3): [1, 2, 3, 4] (ordenado)

Ejemplo 2:

Entrada: [1,2,3]
Salida: []
Explicación: El arreglo ya está ordenado, no se requiere ninguna inversión.

Restricciones:

• 1 ≤ A.length ≤ 100
• A[i] es una permutación de [1, 2, ..., A.length]

Estrategia:

Dado que se permite hasta 10 veces la longitud del arreglo, podemos usar un enfoque por etapas: para cada elemento desde el más grande hasta el más pequeño, lo llevamos a su posición correcta con dos inversiones.

1. Sea L la longitud restante por procesar.
2. Encuentra la posición pos del valor máximo entre los primeros L elementos.
3. Invierte los primeros pos elementos para llevar el máximo al inicio.
4. Invierte los primeros L elementos para llevar el máximo al final (su lugar correcto).
5. Reduce L en 1 y repite hasta que el arreglo esté ordenaod.

Implementación en C++:

class Solution {
public:
    vector<int> pancakeSort(vector<int>& A) {
        vector<int> result;
        int remaining = A.size();
        while (!isSorted(A)) {
            int maxPos = findMaxPos(A, remaining);
            if (maxPos == remaining) {
                remaining--;
            } else {
                result.push_back(maxPos);
                reverse(A, maxPos);
                result.push_back(remaining);
                reverse(A, remaining);
                remaining--;
            }
        }
        return result;
    }
private:
    bool isSorted(vector<int>& arr) {
        for (int i = 1; i < arr.size(); i++)
            if (arr[i-1] > arr[i]) return false;
        return true;
    }
    int findMaxPos(vector<int>& arr, int limit) {
        int idx = 0;
        for (int i = 1; i < limit; i++)
            if (arr[i] > arr[idx]) idx = i;
        return idx + 1; // 1-indexed
    }
    void reverse(vector<int>& arr, int k) {
        int i = 0, j = k - 1;
        while (i < j) swap(arr[i++], arr[j--]);
    }
};

Versión recursiva en Python:

class Solution(object):
    def pancakeSort(self, A):
        if len(A) == 1:
            return []
        max_val = len(A)
        idx = A.index(max_val)  # 0-indexed
        # Invertir para llevar el máximo al inicio
        A[:idx+1] = reversed(A[:idx+1])
        # Invertir todo para llevarlo al final
        A.reverse()
        # Registrar las dos inversiones y continuar con el resto
        return [idx+1, len(A)] + self.pancakeSort(A[:-1])

Ambos enfoques garantizan una solución dentro del límite permitido de inversiones.