Problema A: Máxima suma de subsecuencia

Descripción: Dada una secuencia de enteros a1, a2, …, an, encontrar una susbecuencia contigua ai~aj que maximice la suma de los elementos. Solo se requiere la suma máxima, no la subsecuencia en sí.

Entrada: Una serie de enteros separados por espacios.

Salida: La suma máxima de una subsecuencia.

Ejemplo de entrada:
-2 11 -4 13 -5 -2

Ejemplo de salida:
20

Pistas: El enfoque de fuerza bruta tiene complejidad O(n³), que puede opitmizarse a O(n²). Estos algoritmos pueden ser lentos para secuencias grandes. Usando divide y vencerás, se puede lograr O(n log n). También existe un algoritmo eficiente de O(n) conocido como algoritmo de Kadane. Nota: el número de entradas es desconocido, por lo que se debe leer hasta el fin de la entrada.

Solución (algoritmo de Kadane):

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int calcular_maxima_suma(const vector<int>& datos) {
    int max_global = INT_MIN;
    int max_local = 0;
    for (int elem : datos) {
        max_local = max(elem, max_local + elem);
        if (max_local > max_global) {
            max_global = max_local;
        }
    }
    return max_global;
}

int main() {
    vector<int> secuencia;
    int numero;
    while (cin >> numero) {
        secuencia.push_back(numero);
    }
    cout << calcular_maxima_suma(secuencia) << endl;
    return 0;
}
</int></int></climits></vector></iostream>

Problema B: Conteo de pares invertidos en cadenas

Descripción: Dado un arreglo de cadenas, si una cadena mayor en orden lexicográfico precede a una menor, forman un "par invertido". Encontrar el número total de tales pares.

Entrada: Primero el tamaño n del arreglo, luego n cadenas de longitud 10 separadas por espacios.

Salida: Primero, imprimir la cadena en pinyin "wo yi yue du guan yu chao xi de shuo ming", luego el número total de pares invertidos. Usar un tipo de dato grande para el cotnador.

Ejemplo de entrada:
3 aaaaaaaaaa cccccccccc bbbbbbbbbb

Ejemplo de salida:
wo yi yue du guan yu chao xi de shuo ming<br></br>1

Pistas: Evitar el algoritmo de fuerza bruta que tiene complejidad O(n²). Se puede usar el enfoque de ordenamiento por mezcla para contar pares invertidos de manera eficiente en O(n log n).

Solución (ordenamiento por mezcla con conteo):

#include <iostream>
#include <vector>
#include <string>
using namespace std;

void fusionar(vector<string>& arr, int ini, int med, int fin, long long& cont, vector<string>& aux) {
    for (int i = ini; i <= fin; ++i) {
        aux[i] = arr[i];
    }
    int ptr1 = ini;
    int ptr2 = med + 1;
    for (int i = ini; i <= fin; ++i) {
        if (ptr1 == med + 1) {
            while (ptr2 <= fin) {
                arr[i++] = aux[ptr2++];
            }
            break;
        }
        if (ptr2 == fin + 1) {
            while (ptr1 <= med) {
                arr[i++] = aux[ptr1++];
            }
            break;
        }
        if (aux[ptr1] <= aux[ptr2]) {
            arr[i] = aux[ptr1];
            ++ptr1;
        } else {
            cont += med - ptr1 + 1;
            arr[i] = aux[ptr2];
            ++ptr2;
        }
    }
}

void ordenar_por_fusion(vector<string>& arr, int ini, int fin, long long& cont, vector<string>& aux) {
    if (ini < fin) {
        int med = (ini + fin) / 2;
        ordenar_por_fusion(arr, ini, med, cont, aux);
        ordenar_por_fusion(arr, med + 1, fin, cont, aux);
        fusionar(arr, ini, med, fin, cont, aux);
    }
}

int main() {
    int n;
    cin >> n;
    vector<string> arreglo(n);
    for (int i = 0; i < n; ++i) {
        cin >> arreglo[i];
    }
    vector<string> ayuda(n);
    long long pares_inv = 0;
    ordenar_por_fusion(arreglo, 0, n - 1, pares_inv, ayuda);
    cout << "wo yi yue du guan yu chao xi de shuo ming" << endl;
    cout << pares_inv << endl;
    return 0;
}
</string></string></string></string></string></string></string></vector></iostream>