Implementación del algoritmo del programador: el mejor momento para comprar y vender acciones
Utiliza dos variables:
Variable mínima: indica el valor mínimo antes de recorrer la posición.
Variable Max: representa la ganancia máxima que se debe vender en la posición actual I.
Atraviesa la matriz una vez. Al atravesar la posición I, la lógica de actualización de los valores mínimo y máximo es la siguiente:
Después de atravesar la matriz, el valor máximo devuelto es la respuesta final. El código completo se muestra en:
Tema: debido a que podemos negociar cualquier cantidad de veces, pero solo podemos mantener una acción a la vez, podemos capturar todos los segmentos ascendentes de la curva de acciones y el rendimiento acumulado. es el rendimiento máximo. Recorre la matriz y resta el valor de la posición anterior de la posición atravesada. Si es positivo, acéptalo. Si es negativo, establece el beneficio actual en 0 (lo que indica que la transacción aún no se ha realizado). Repita la matriz una vez y no se perderá todas las ganancias.
Establezca una variable máxima con un valor inicial de 0 para recopilar el valor máximo de ingresos. Para la posición I, la lógica de actualización máxima es la siguiente:
El código completo es el siguiente:
De esta pregunta podemos simplemente sacar una conclusión: si el número de elementos de la matriz es N, entonces el máximo La ejecución de N/2 transacciones puede capturar todos los valores crecientes (en casos extremos, compre en el momento actual y venda en el momento siguiente, y mantenga esta transacción hasta el final, el número de transacciones ejecutadas es N /2).
Punto principal:
En el segundo caso, definimos
donde dp[i][j] significa en [0...i] . Si se puede completar la tabla bidimensional de dp, entonces el valor de dp[N-1][k] devuelto es la respuesta clave.
En la matriz bidimensional dp,
El valor de la primera fila representa el retorno máximo de varias transacciones dentro del rango de la matriz [0]..0], que es obviamente 0.
El valor de la primera columna representa el beneficio máximo obtenido al operar 0 veces en el rango del array [0]...i], y obviamente, también es 0.
Para cualquier valor de la posición pública dp[i][j],
Podemos enumerar si la posición I participa en la transacción. Si la posición I no participa en la transacción, entonces dp[i][j] = dp[i-1][j]. Si la posición I participa en la transacción, entonces la posición I debe ser la última oportunidad de venta.
El momento de la última compra puede ser el siguiente:
La última compra fue en la posición I, entonces DP[I][J]= DP[I][J-1 ]- ARR[I]+ARR[I].
El último momento de compra es en i-1, por lo que DP[I][J]= DP[I-1][J-1]-ARR[I-1]+ARR[I].
La última compra fue en la posición i-2, luego DP[I][J]= DP[I-2][J-1]-ARR[I-2]+ARR[I] .
...
La última compra fue en la posición 0, entonces DP[I][J]= DP[0][J-1]-ARR[0]+ ARR [I].
El código completo es el siguiente:
El código anterior contiene un comportamiento de enumeración.
Esta enumeración se puede optimizar aumentando la complejidad del tiempo.
Podemos dar un ejemplo específico para ilustrar cómo optimizar.
Por ejemplo,
Cuando encontramos el valor de dp[5][3] Cuando. , puede enumerar si la posición 5 participa en la transacción. Suponga que la posición 5 no participa en la transacción, luego dp [5] [3] = dp [4] [3]. Debe ser la última oportunidad de vender. El momento de la última compra puede ser el siguiente:
La última compra fue en la posición 5, entonces DP[5][3]= DP[5][2]-ARR[5]+ARR[ 5] .
La última compra fue en la posición 4, entonces DP[5][3]= DP[4][2]-ARR[4]+ARR[5].
La última compra fue en la posición 3, entonces DP[5][3]= DP[3][2]-ARR[3]+ARR[5].
El último momento de compra es en la posición 2, por lo que DP[5][3]= DP[2][2]-ARR[2]+ARR[5].
El último momento de compra es en la posición 1, por lo que DP[5][3]= DP[1][2]-ARR[1]+ARR[5].
La última compra fue en la posición 0, entonces DP[5][3]= DP[0][2]-ARR[0]+ARR[5].
Encontramos el valor de dp[4][3], y podemos enumerar si la posición 4 participa en la transacción. Suponiendo que la posición 4 no participa en la transacción, entonces dp[4][3] = dp[3][3]. Suponiendo que la posición 4 participa en la transacción, entonces la posición 4 debe ser la última oportunidad de venta. El momento de la última compra puede ser el siguiente:
La última compra fue en la posición 4, entonces DP[4][3]= DP[4][2]-ARR[4]+ARR[ 4] .
La última compra fue en la posición 3, entonces DP[4][3]= DP[3][2]-ARR[3]+ARR[4].
La última compra fue en la posición 2, entonces DP[4][3]= DP[2][2]-ARR[2]+ARR[4].
El último momento de compra es en la posición 1, por lo que DP[4][3]= DP[1][2]-ARR[1]+ARR[4].
La última compra fue en la posición 0, luego DP[4][3]= DP[0][2]-ARR[0]+ARR[4].
Comparando las dependencias entre dp[5][3] y dp[4][3], podemos sacar las siguientes conclusiones:
Supongamos que estamos buscando dp[4] En el proceso de [3], podemos obtener el valor máximo de la siguiente fórmula de recursividad.
dp[4][2] - arreglo[4]
dp[3][2] - arreglo[3]
dp[2][ 2] - arreglo[2]
dp[1][2] - arreglo[1]
dp[0][2] - arreglo[0]
Definimos el valor máximo de la fórmula anterior como mejor, entonces
dp[5][3] = Math.max(dp[4][3], math. max(DP[5] [ 2]-arr[5]+arr[5], best + arr[5]))
Entonces dp[5][3] se puede acelerar desde dp[4][3],
De manera similar,
Dp[4][3] se puede obtener acelerando dp[3][3].
Dp[3][3] se puede obtener acelerando dp[2][3].
Dp[2][3] se puede obtener acelerando dp[1][3].
Dp[1][3]Es fácil concluir que dp[1][3] tiene las siguientes posibilidades:
Posibilidad 1, la posición 1 no participa en absoluto, entonces
Posibilidad 2, 1 es la última oportunidad de venta y la oportunidad de compra es 1.
Posibilidad 3, la posición 1 es la última oportunidad de venta y la oportunidad de compra es la posición 0.
En este momento, el valor de mejor es
Luego acelere dp[2][3] hasta dp[1] y acelere dp[3][hasta dp[2]. [3] 3]..., entonces el método de llenado de DP bidimensional es llenar las columnas.
Complete dp[1][0], dp[1][2] hasta dp[1][k], complete la primera columna
Luego complete dp; [2 ][0], dp[2][1] a dp[2][k], complete la segunda columna
...
Complete cada columna; a su vez, hasta completar la columna N-1.
El comportamiento de la enumeración ha sido optimizado. El código completo después de optimizar la enumeración es el siguiente:
Propósito: Sea k=2 la respuesta a la pregunta anterior.
Propósito: Debido al período de congelación, cada posición tiene tres estados:
Definir tres matrices, que representan el valor máximo de la posición I en estas tres situaciones.
Obviamente, existen las siguientes conclusiones:
Para la posición general I
El beneficio máximo es el máximo de los tres métodos anteriores. El código completo se muestra en:
Debido a que las tres matrices tienen una relación recursiva, se pueden usar tres variables en lugar de tres matrices para lograr la compresión del espacio. El código optimizado es el siguiente:
Principio: debido a que no hay período de congelación, la posición I tiene solo dos estados.
Para la posición 0
Para la posición universal i
El código completo es el siguiente:
De manera similar, ambos arreglos tienen una relación de recursividad y puede comprimirse espacialmente. El código simplificado es el siguiente:
Enlace original: El mejor momento para comprar y vender acciones - Huizeng - Blog Garden