LOS 10 MEJORES ALGORITMOS DE MATRICES

 

 

1.- Invertir cadena sin afectar caracteres especiales

2.- En una lista, encuentra particiones de palíndromos

3.- Contar trillizos con una suma menor que un valor dado

4.- Convertir la matriz en la moda Zig-Zag

5.- Generar todas las matrices ordenadas a partir de elementos alternativos de dos matrices ordenadas dadas

6.- Trillizo de Pitágoras en un conjunto

7.- Longitud del mayor sub-arreglo con elementos contiguos

8.- Encontrar el valor entero positivo más pequeño que no puede ser representado como la suma de cualquier subconjunto de un conjunto dado

9.- El subconjunto más pequeño con una suma mayor que un valor dado

10.- Compra y venta de acciones para maximizar el beneficio

 

&&&&&&&&&&

&&&&&&&

&&&

&

 

 

 

1.- Invertir una cadena sin afectar a los caracteres especiales

 

Dada una cadena, que contiene caracteres especiales junto con los alfabetos ('a' a 'z' y 'A' a 'Z'), invierta la cadena de manera que los caracteres especiales no se vean afectados

Ejemplo:

Entrada:   str = "a,b$c"

Salida:  str = "c,b$a"

El carácter $ no se mueve, solo la subsecuenciaabc

Entrada:   str = "Ab,c,de!$"

Salida:  str = "ed,c,bA!$"

Solución sencilla:

1) Crear una matriz de caracteres temporales, digamos temp[].

2) Copiar los caracteres alfabéticos de la matriz dada a temp[].

3) Invertir temp[] usando un algoritmo estándar de inversión de cadenas.

4) Ahora cruza la cadena de entrada y temp en un solo bucle. Donde quiera que haya un carácter alfabético en la cadena de entrada, reemplácelo por el carácter actual de temp[].

 

Solución eficiente:

La complejidad temporal de la solución anterior es O(n), pero requiere espacio adicional y hace dos travesías de la cadena de entrada.

Podemos invertir con una travesía y sin espacio extra. A continuación se muestra el algoritmo. Veamos:

 

1) Que la cadena de entrada sea "str[]" y la longitud de la cadena sea "n".

2) l = 0, r = n-1

3) Mientras que l es más pequeño que r, haga lo siguiente

    a) Si str[l] no es un carácter alfabético, haga l++

    b) Si no, si no es un carácter alfabético, entonces...

    c) Intercambiar las tiras y las tiras

 

A continuación se muestran las implementaciones del algoritmo anterior, en lenguaje C++.

#include<bits/stdc++.h>

usando namespace std;

 

bool isAlphabet(char x)

{ retorno ( (x >= 'A' && x <= 'Z') ||     (x >= 'a' && x <= 'z') );

}

 

void reverse(char str[])

{  // Iniciar los punteros izquierdo y derecho

    int r = strlen(str) - 1, l = 0;

 

    // Atravesar desde ambos extremos hasta   'l' y 'r'  mientras que (l < r)

    {

        // Ignorar los especiales

        If  (!es Alfabeto(str[l]))

            l++;

        else if (!es Alfabeto(str[r]))

            r--;

        {

            swap(str[l], str[r]);

            l++;

            r--;

        }

    }

}

 

// Código principal

int main()

{

    char str[] = "a!!!b.c.d,e'f,ghi";

    cout << "Cadena de entrada: " << str <<< endl;

    reverse(str);

    cout << "Cadena de salida: " << str <<< endl;

    retorno 0;

}

 

Cadena de entrada: a!!!b.c.d,e'f,ghi

Cadena de salida: i!!! h.g.f, e'd, cba

 

 

 

2.- Dada una lista, imprime todas las particiones de palíndromos posibles

 

Dada una ristra, encontrar todas las posibles particiones palindromicas de una ristra dada.

 

Nótese que este problema es diferente del problema de partición del Palíndromo, allí la tarea era encontrar la partición con cortes mínimos en la cadena de entrada. Aquí necesitamos imprimir todas las particiones posibles.

 

La idea es revisar cada subcadena empezando por el primer carácter, comprobar si es el palíndromo. Si es así, entonces agregar la subcadena a la solución y recurrir para la parte restante. Abajo está el algoritmo completo.

 

#include<bits/stdc++.h>

using namespace std;

  

bool isPalindrome(string str, int low, int high)

{

    while (low < high)

    {

        if (str[low] != str[high])

            return false;

        low++;

        high--;

    }

    return true;

}

  

// Función recursiva para encontrar todas las particiones palindricas de str[start..n-1]

// allPart --> Un vector de cuerdas. Cada vector dentro de él almacena

// una partición

// currPart --> Un vector de cuerdas para almacenar la partición actual 

void allPalPartUtil(vector<vector<string> >&allPart, vector<string> &currPart

                   int start, int n, string str)

{

    // If 'start' has reached len

    if (start >= n)

    {

        allPart.push_back(currPart);

        return;

    }

  

    for (int i=start; i<n; i++)

    {

        if (isPalindrome(str, start, i))

        {

            currPart.push_back(str.substr(start, i-start+1));

  

            allPalPartUtil(allPart, currPart, i+1, n, str);

              

            currPart.pop_back();

        }

    }

}

  

void allPalPartitions(string str)

{

    int n = str.length();

  

    vector<vector<string> > allPart;

    vector<string> currPart

    allPalPartUtil(allPart, currPart, 0, n, str);

  

    for (int i=0; i< allPart.size(); i++ )

    {

        for (int j=0; j<allPart[i].size(); j++)

            cout << allPart[i][j] << " ";

        cout << "\n";

    }

}

  

// Principal

int main()

{

    string str = "nitin";

    allPalPartitions(str);

    return 0;

}

 

 

3.- Contar trillizos con una suma menor que un valor dado

 

Dada una serie de números enteros distintos y un valor de suma. Encuentra el recuento de trillizos con una suma menor que el valor de la suma dada. La complejidad de tiempo esperada es O(n2).

 

Ejemplo:

Entrada : arr[] = {-2, 0, 1, 3}

        suma = 2.

Salida: 2

Explicación: Abajo hay trillizos con una suma inferior a 2

               (-2, 0, 1) y (-2, 0, 3)

 

1) Ordena la matriz de entrada en orden creciente.

2) Inicializar el resultado como 0.

3) Ejecuta un bucle de i = 0 a n-2.  Una iteración de este bucle encuentra todo

   trillizos con arresto como primer elemento.

     a) Inicializar otros dos elementos como elementos de esquina del subconjunto

        arr[i+1..n-1], es decir, j = i+1 y k = n-1

     b) Mueve j y k hacia el otro hasta que se encuentren, es decir, mientras que (j = suma), entonces haz k--

 

            // Si no, para las corrientes i y j, puede (k-j) haber terceros elementos posibles

            // que satisfacen la restricción.

            (ii) Else Do ans += (k - j) seguido de j++

 

#include<bits/stdc++.h>

using namespace std;

  

int countTriplets(int arr[], int n, int sum)

{

    sort(arr, arr+n);

  

    int ans = 0;

  

    for (int i = 0; i < n - 2; i++)

    {

        int j = i + 1, k = n - 1;

  

        while (j < k)

        {

            if (arr[i] + arr[j] + arr[k] >= sum)

                k--;

  

            else

            {

                ans += (k - j);

                j++;

            }

        }

    }

    return ans;

}

  

// Principal

int main()

{

    int arr[] = {5, 1, 3, 4, 7};

    int n = sizeof arr / sizeof arr[0];

    int sum = 12;

    cout << countTriplets(arr, n, sum) << endl;

    return 0;

}

Salida: 4

 

 

4.- Convertir la matriz en la moda Zig-Zag

 

Dada una serie de elementos DISTINTOS, reorganice los elementos de la serie en zig-zag en tiempo O(n). El arreglo convertido debe ser en forma a < b > c < d > e < f.

Ejemplo:

Entrada: arr[] = {4, 3, 7, 8, 6, 2, 1}

Salida: arr[] = {3, 7, 4, 8, 2, 6, 1}

 

Una solución simple es ordenar primero el conjunto. Después de ordenar, excluir el primer elemento, intercambiar los elementos restantes en parejas. (es decir, mantener el arr[0] tal cual, intercambiar el arr[1] y el arr[2], intercambiar el arr[3] y el arr[4], y así sucesivamente).

 

Complejidad del tiempo: O(N log N) ya que necesitamos ordenar la matriz primero

Podemos convertir en O(n) tiempo usando un enfoque eficiente. La idea es utilizar una modificación de una pasada de tipo burbuja.

 

Mantener una bandera para representar qué orden(es decir, < o >) necesitamos actualmente.

Si los dos elementos actuales no están en ese orden, entonces intercambien esos elementos, de lo contrario no.

Veamos la lógica principal usando tres elementos consecutivos A, B, C.

 

Supongamos que estamos procesando B y C actualmente y la relación actual es '<', pero tenemos B > C. Como la relación actual es '<' la relación anterior debe ser '>' es decir, A debe ser mayor que B. Entonces, la relación es A > B y B > C. Podemos deducir A > C. Entonces si intercambiamos B y C entonces la relación es A > C y C < B. Finalmente obtenemos el orden deseado A C B

 

#include <iostream

using namespace std

  

void zigZag(int arr[], int n) 

    // La bandera verdadera indica la relación "<" se espera, 

    // Si no, se espera ">". La primera relación esperada 

    // es "<" 

    bool flag = true; 

  

    for (int i=0; i<=n-2; i++) 

    { 

        if (flag)

        { 

            /* Si tenemos una situación como A > B > C, 

            obtenemos A > B < C cambiando B y C */

             if (arr[i] > arr[i+1]) 

                swap(arr[i], arr[i+1]); 

        } 

        else        { 

            /* Si tenemos una situación como A < B < C, 

            obtenemos A < C > B intercambiando B y C */

            if (arr[i] < arr[i+1]) 

                swap(arr[i], arr[i+1]); 

        } 

        flag = !flag;

    } 

  

// Principal 

int main() 

    int arr[] = {4, 3, 7, 8, 6, 2, 1}; 

    int n = sizeof(arr)/sizeof(arr[0]); 

    zigZag(arr, n); 

    for (int i=0; i<n; i++) 

        cout << arr[i] << " "; 

    return 0; 

Salida:     3    7    4    8    2    6    1

Complejidad temporal: O(n)
Espacio auxiliar: O(1)

 

 

5.- Generar todas las matrices ordenadas a partir de elementos alternativos de dos matrices ordenadas dadas

 

Dados dos arreglos ordenados A y B, genera todos los arreglos posibles de tal manera que el primer elemento se toma de A, luego de B, luego de A y así sucesivamente en orden creciente hasta que los arreglos se agoten. Las matrices generadas deben terminar con un elemento de B.

 

Por ejemplo

A = {10, 15, 25}

B = {1, 5, 20, 30}

 

Los arreglos resultantes son:

  10 20

  10 20 25 30

  10 30

  15 20

  15 20 25 30

  15 30

  25 30

Le recomendamos encarecidamente que minimice su navegador y lo pruebe usted mismo primero.

 

La idea es usar la recursión. En la función recursiva, se pasa una bandera para indicar si el elemento actual en la salida debe ser tomado de 'A' o 'B'. A continuación se muestra la implementación de C++.

 

#include<bits/stdc++.h>

using namespace std;

  

void printArr(int arr[], int n);

  

/* La función de generar e imprimir todos los conjuntos ordenados de elementos alternativos de

   A[i..m-1]' y 'B[j..n-1]'.

   Si "bandera" es cierto, entonces el elemento actual debe ser incluido desde A, de lo contrario

   de B.

   'len' es el índice en la matriz de salida C[]. Imprimimos la matriz de salida cada vez

   antes de incluir un carácter de A sólo si la longitud de la matriz de salida es

   mayor que 0. Intentamos que todas las combinaciones posibles

 */

void generateUtil(int A[], int B[], int C[], int i, int j, int m, int n,

                  int len, bool flag)

{

    if (flag)    {

        if (len) printArr(C, len+1);

  

        for (int k = i; k < m; k++)

        {

            if (!len)

            {

                /* este bloque funciona para que la primera llamada incluya

                     el primer elemento de la matriz de salida

*/

                C[len] = A[k];

  

                generateUtil(A, B, C, k+1, j, m, n, len, !flag);

            }

            else                {

                if (A[k] > C[len])

                {

                    C[len+1] = A[k];

                    generateUtil(A, B, C, k+1, j, m, n, len+1, !flag);

                }

            }

        }

    }

    else      {

        for (int l = j; l < n; l++)

        {

            if (B[l] > C[len])

            {

                C[len+1] = B[l];

                generateUtil(A, B, C, i, l+1, m, n, len+1, !flag);

            }

        }

    }

}

  

void generate(int A[], int B[], int m, int n)

{

    int C[m+n];  

    generateUtil(A, B, C, 0, 0, m, n, 0, true);

}

  

void printArr(int arr[], int n)

{

    for (int i = 0; i < n; i++)

        cout << arr[i] << " ";

    cout << endl;

}

  

// Principal

int main()

{

    int A[] = {10, 15, 25};

    int B[] = {5, 20, 30};

    int n = sizeof(A)/sizeof(A[0]);

    int m = sizeof(B)/sizeof(B[0]);

    generate(A, B, n, m);

    return 0;

}

Salida:

10 20

10 20 25 30

10 30

15 20

15 20 25 30

15 30

25 30

 

 

6.- Trillizo de Pitágoras en un conjunto

 

Dada una matriz de números enteros, escribe una función que devuelva verdadera si hay un triplete (a, b, c) que satisfaga a2 + b2 = c2.

Ejemplo:

Entrada: arr[] = {3, 1, 4, 6, 5}

Salida: Verdadero

Hay un trillizo pitagórico (3, 4, 5).

 

Podemos resolver esto en tiempo de O(n2) clasificando la matriz primero.

1) Haz un cuadrado de cada elemento de la matriz de entrada. Este paso lleva O(n) tiempo.

2) Ordena la matriz cuadrada en orden creciente. Este paso lleva O(nLogn) tiempo.

3) Para encontrar un triplete (a, b, c) de tal manera que a2 = b2 + c2, haz lo siguiente.

 

Fijar 'a' como último elemento de la matriz ordenada.

Ahora busque el par (b, c) en la submatriz entre el primer elemento y 'a'. Un par (b, c) con una suma dada puede ser encontrado en el tiempo de O(n) usando el algoritmo de encuentro en el medio discutido en el método 1 de este post.

Si no se encuentra un par para la actual "a", entonces mueva "a" una posición hacia atrás y repita el paso 3.2.

 

 

#include <algorithm>

#include <iostream>

  

using namespace std;

  

// Devuelve verdadero si hay un trillizo con la siguiente propiedad

// A[i]*A[i] = A[j]*A[j] + A[k]*[k]

// Tenga en cuenta que esta función modifica el conjunto dado

bool isTriplet(int arr[], int n)

{

    for (int i = 0; i < n; i++)  arr[i] = arr[i] * arr[i];

    sort(arr, arr + n);

  

    for (int i = n - 1; i >= 2; i--) {

        // Para encontrar los otros dos elementos, inicia dos índices

        // ...variables de dos esquinas del conjunto y se mueven...

        // ellos hacia el otro

        int l = 0;

        int r = i - 1;

        while (l < r) {

            if (arr[l] + arr[r] == arr[i])

                return true;

  

            (arr[l] + arr[r] < arr[i]) ? l++ : r--;

        }

    }

  

    return false;

}

  

//Principal

int main()

{

    int arr[] = { 3, 1, 4, 6, 5 };

    int arr_size = sizeof(arr) / sizeof(arr[0]);

    isTriplet(arr, arr_size) ? cout << "Yes" : cout << "No";

    return 0;

}

Salida:    Si

Complejidad: O(n^2)

 

 

7.- Longitud del mayor sub-arreglo con elementos contiguos

 

Dada una serie de números enteros distintos, encuentre la longitud del subconjunto más largo que contenga números que puedan ser ordenados en una secuencia continua.

Ejemplo:

Entrada: arr[] = {10, 12, 11};

Salida: Longitud del subconjunto contiguo más largo

 

Recomendamos encarecidamente que minimice el navegador e intente esto usted mismo primero.

 

Lo importante que hay que tener en cuenta es que todos los elementos son distintos. Si todos los elementos son distintos, entonces un subconjunto tiene elementos contiguos si y sólo si la diferencia entre los elementos máximos y mínimos del subconjunto es igual a la diferencia entre el último y el primer índice del subconjunto. Por lo tanto, la idea es llevar la cuenta de los elementos mínimos y máximos en cada submatriz.

 

#include<iostream>

using namespace std;

  

// Funciones de utilidad para encontrar el mínimo y el máximo de

// dos elementos int min(int x, int y) { return (x < y)? x : y; }

int max(int x, int y) { return (x > y)? x : y; }

  

// Devuelve la longitud del subarreglo contiguo más largo

int findLength(int arr[], int n)

{

    int max_len = 1; 

    for (int i=0; i<n-1; i++)

    {

        int mn = arr[i], mx = arr[i];

        for (int j=i+1; j<n; j++)

        {

            mn = min(mn, arr[j]);

            mx = max(mx, arr[j]);

  

            if ((mx - mn) == j-i)

                max_len = max(max_len, mx-mn+1);

        }

    }

    return max_len;  // Return result

}

  

// Principal

int main()

{

    int arr[] = {1, 56, 58, 57, 90, 92, 94, 93, 91, 45};

    int n = sizeof(arr)/sizeof(arr[0]);

    cout << " La longitud del subconjunto contiguo más largo es de "

         << findLength(arr, n);

    return 0;

}

Salida: La longitud del subconjunto contiguo más largo es de 5

La complejidad temporal de la solución anterior es O(n2).

 

 

 

8.- Encontrar el valor entero positivo más pequeño que no puede ser representado como la suma de cualquier subconjunto de un conjunto dado

 

Dada una matriz ordenada (ordenada en orden no decreciente) de números positivos, encuentre el valor entero positivo más pequeño que no pueda representarse como suma de elementos de ningún subconjunto del conjunto dado.

La complejidad temporal esperada es O(n).

 

Ejemplo:

Entrada: arr[] = {1, 3, 6, 10, 11, 15};

Salida: 2

 

Una solución sencilla es empezar desde el valor 1 y comprobar todos los valores uno por uno si pueden sumarse a los valores de la matriz dada. Esta solución es muy ineficiente ya que reduce al problema de la suma de subconjuntos que es un conocido problema completo de NP.

 

Podemos resolver este problema en O(n) tiempo usando un simple bucle. Dejemos que el array de entrada sea arr[0..n-1]. Inicializamos el resultado como 1 (el resultado más pequeño posible) y atravesamos el array dado. Dejemos que el elemento más pequeño que no puede ser representado por los elementos en los índices de 0 a (i-1) sea 'res', hay dos posibilidades siguientes cuando consideramos el elemento en el índice i:

 

1) Decidimos que "res" es el resultado final: Si arr[i] es mayor que 'res', entonces encontramos la brecha que es 'res' porque los elementos después de arr[i] también van a ser mayores que 'res'.

 

2) El valor de "res" se incrementa después de considerar el arr[i]: El valor de 'res' se incrementa por arr[i] (¿por qué? Si los elementos de 0 a (i-1) pueden representar 1 a 'res-1', entonces los elementos de 0 a i pueden representar 1 a 'res + arr[i] - 1' estarían añadiendo 'arr[i]' a todos los subconjuntos que representan 1 a 'res')

 

#include <bits/stdc++.h>

using namespace std;

 

// Devuelve el número más pequeño que no puede ser representado como suma

// del subconjunto de elementos del conjunto representado por el conjunto ordenado arr[0..n-1]

int findSmallest(int arr[], int n)

{

int res = 1; // Initialize result

 

// Atravesar la matriz e incrementar la 'res' si la arr[i] es

// más pequeño o igual a 'res'.

for (int i = 0; i < n && arr[i] <= res; i++)

            res = res + arr[i];

 

return res;

}

 

// Principal

int main()

{

int arr1[] = {1, 3, 4, 5};

int n1 = sizeof(arr1)/sizeof(arr1[0]);

cout << findSmallest(arr1, n1) << endl;

 

int arr2[] = {1, 2, 6, 10, 11, 15};

int n2 = sizeof(arr2)/sizeof(arr2[0]);

cout << findSmallest(arr2, n2) << endl;

 

int arr3[] = {1, 1, 1, 1};

int n3 = sizeof(arr3)/sizeof(arr3[0]);

cout << findSmallest(arr3, n3) << endl;

 

int arr4[] = {1, 1, 3, 4};

int n4 = sizeof(arr4)/sizeof(arr4[0]);

cout << findSmallest(arr4, n4) << endl;

 

return 0;

}

Salida: 2   4   5   10

Complejidad: O(n)

 

 

9.- El subconjunto más pequeño con una suma mayor que un valor dado

 

Dada una matriz de números enteros y un número x, encuentra la submatriz más pequeña con una suma mayor que el valor dado.

Ejemplo:

arr[] = {1, 4, 45, 6, 0, 19}

   x = 51

Salida: 3

La longitud mínima del subgrupo es de {4, 45, 6}

Solución eficiente: Este problema puede ser resuelto en O(n) tiempo usando la idea usada en este post

 

#include <iostream>

using namespace std;

  

// Devuelve la longitud del subconjunto más pequeño con una suma mayor que x.

// Si no hay un subconjunto con la suma dada, entonces devuelve n+1

int smallestSubWithSum(int arr[], int n, int x)

{

    int curr_sum = 0, min_len = n+1;

  

    int start = 0, end = 0;

    while (end < n)

    {

        // Sigue añadiendo elementos de la matriz mientras la suma actual

        // es más pequeño que x

        while (curr_sum <= x && end < n)

            curr_sum += arr[end++];

  

        while (curr_sum > x && start < n)

        {

            if (end - start < min_len)

                min_len = end - start;

  

            curr_sum -= arr[start++];

        }

    }

    return min_len;

}

  

  

//Principal

int main()

{

    int arr1[] = {1, 4, 45, 6, 10, 19};

    int x = 51;

    int n1 = sizeof(arr1)/sizeof(arr1[0]);

    int res1 = smallestSubWithSum(arr1, n1, x);

    (res1 == n1+1)? cout << "Not possible\n" :

                    cout << res1 << endl;

  

    int arr2[] = {1, 10, 5, 2, 7};

    int n2 = sizeof(arr2)/sizeof(arr2[0]);

    x  = 9;

    int res2 = smallestSubWithSum(arr2, n2, x);

    (res2 == n2+1)? cout << "Not possible\n" :

                    cout << res2 << endl;

  

    int arr3[] = {1, 11, 100, 1, 0, 200, 3, 2, 1, 250};

    int n3 = sizeof(arr3)/sizeof(arr3[0]);

    x  = 280;

    int res3 = smallestSubWithSum(arr3, n3, x);

    (res3 == n3+1)? cout << "Not possible\n" :

                    cout << res3 << endl;

  

    return 0;

}

Salida:   3    1    4

 

 

10.- Compra y venta de acciones para maximizar el beneficio

 

El costo de una acción en cada día se da en una matriz, encuentra la máxima ganancia que puedes hacer comprando y vendiendo en esos días. Por ejemplo, si la matriz dada es {100, 180, 260, 310, 40, 535, 695}, el máximo beneficio puede obtenerse comprando en el día 0, vendiendo en el día 3. Otra vez compra en el día 4 y vende en el día 6. Si la serie de precios dada se ordena en orden decreciente, entonces no se puede obtener ningún beneficio.

Si se nos permite comprar y vender una sola vez, entonces podemos usar el siguiente algoritmo. Diferencia máxima entre dos elementos. Aquí se nos permite comprar y vender varias veces.

El siguiente algoritmo es para este problema.

Encuentra los mínimos locales y guárdalos como índice de partida. Si no existe, regresa.

Encuentra los máximos locales y guárdalos como índice final. Si llegamos al final, guardad el final como índice final.

Actualiza la solución (Incrementa la cuenta de pares de compra-venta)

Repita los pasos anteriores si no se alcanza el final.

 

#include <bits/stdc++.h>

using namespace std;

  

// Esta función encuentra la compra-venta

// programa para el máximo beneficio

void stockBuySell(int price[], int n)

{

    if (n == 1)    return;

  

    int i = 0;

    while (i < n - 1) {

  

        // Encuentra los mínimos locales

        // Tenga en cuenta que el límite es (n-2) como estamos

        // comparando el elemento actual con el siguiente elemento

        while ((i < n - 1) && (price[i + 1] <= price[i]))

            i++;

  

        // Si llegamos al final, rompe

        // como ninguna otra solución posible

        if (i == n - 1)   break;

        int buy = i++;

  

        // Encuentra los máximos locales

        // Tenga en cuenta que el límite es (n-1) como estamos

        // comparando con el elemento anterior

        while ((i < n) && (price[i] >= price[i - 1]))

            i++;

 

        int sell = i - 1;

  

        cout << "Buy on day: " << buy

             << "\t Sell on day: " << sell << endl;

    }

}

  

//Principal

int main()

{

    int price[] = { 100, 180, 260, 310, 40, 535, 695 };

    int n = sizeof(price) / sizeof(price[0]);

  

    stockBuySell(price, n);

  

    return 0;

}

Salida:

Compra en el día : 0 Vende en el día: 3

Comprar en el día: 4 Vender en el día: 6

 

Complejidad temporal: El bucle exterior corre hasta que la i se convierte en n-1. Los dos bucles internos incrementan el valor de i en cada iteración. Así que la complejidad temporal global es O(n)

 

 

&&&&&&&&&&&&&

&&&&&&&&&

&&&

&