LeetCode – Mejor momento para comprar y vender acciones III (Java)

Supongamos que tiene una matriz para la que el i-ésimo elemento es el precio de una acción determinada el día i.

Diseñe un algoritmo para encontrar el máximo beneficio. Puede completar como máximo dos transacciones.

Nota:
Una transacción es una compra y una venta. No puede realizar varias transacciones al mismo tiempo (es decir, debe vender las acciones antes de volver a comprar).

Análisis

En comparación con I y II, III limita el número de transacciones a 2. Esto se puede resolver «dividir y conquistar». Usamos izquierda[i] para rastrear el beneficio máximo de las transacciones antes de i, y usar el derecho[i] para rastrear el beneficio máximo para transacciones después de i. Puede utilizar el siguiente ejemplo para comprender la solución de Java:

Prices: 1 4 5 7 6 3 2 9
left = [0, 3, 4, 6, 6, 6, 6, 8]
right= [8, 7, 7, 7, 7, 7, 7, 0]

El beneficio máximo = 13

Solución Java

public int maxProfit(int[] prices) {
	if (prices == null || prices.length < 2) {
		return 0;
	}
 
	//highest profit in 0 ... i
	int[] left = new int[prices.length];
	int[] right = new int[prices.length];
 
	// DP from left to right
	left[0] = 0; 
	int min = prices[0];
	for (int i = 1; i < prices.length; i++) {
		min = Math.min(min, prices[i]);
		left[i] = Math.max(left[i - 1], prices[i] - min);
	}
 
	// DP from right to left
	right[prices.length - 1] = 0;
	int max = prices[prices.length - 1];
	for (int i = prices.length - 2; i >= 0; i--) {
		max = Math.max(max, prices[i]);
		right[i] = Math.max(right[i + 1], max - prices[i]);
	}
 
	int profit = 0;
	for (int i = 0; i < prices.length; i++) {
		profit = Math.max(profit, left[i] + right[i]);
	}
 
	return profit;
}