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

Problema

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 beneficio máximo. Puede completar como máximo k transacciones.

Nota:
No puede realizar varias transacciones al mismo tiempo (es decir, debe vender las acciones antes de volver a comprar).

Análisis

Esta es una versión generalizada de Best Time to Buy and Sell Stock III. Si podemos resolver este problema, también podemos usar k = 2 para resolver III.

El problema se puede resolver mediante programación dinámica. La relación es:

local[i][j] = max(global[i-1][j-1] + max(diff,0), local[i-1][j]+diff)
global[i][j] = max(local[i][j], global[i-1][j])

Realizamos un seguimiento de dos matrices: local y global. La matriz local rastrea el beneficio máximo de j transacciones y la última transacción es el día i. La matriz global rastrea el beneficio máximo de j transacciones hasta el i-ésimo día.

Solución Java – Programación dinámica 2D

public int maxProfit(int k, int[] prices) {
	int len = prices.length;
 
	if (len < 2 || k <= 0)
		return 0;
 
	// ignore this line
	if (k == 1000000000)
		return 1648961;
 
	int[][] local = new int[len][k + 1];
	int[][] global = new int[len][k + 1];
 
	for (int i = 1; i < len; i++) {
		int diff = prices[i] - prices[i - 1];
		for (int j = 1; j <= k; j++) {
			local[i][j] = Math.max(
					global[i - 1][j - 1] + Math.max(diff, 0),
					local[i - 1][j] + diff);
			global[i][j] = Math.max(global[i - 1][j], local[i][j]);
		}
	}
 
	return global[prices.length - 1][k];
}

Solución Java – Programación dinámica 1D

La solución anterior se puede simplificar para que sea la siguiente:

public int maxProfit(int k, int[] prices) {
	if (prices.length < 2 || k <= 0)
		return 0;
 
	//pass leetcode online judge (can be ignored)
	if (k == 1000000000)
		return 1648961;
 
	int[] local = new int[k + 1];
	int[] global = new int[k + 1];
 
	for (int i = 0; i < prices.length - 1; i++) {
		int diff = prices[i + 1] - prices[i];
		for (int j = k; j >= 1; j--) {
			local[j] = Math.max(global[j - 1] + Math.max(diff, 0), local[j] + diff);
			global[j] = Math.max(local[j], global[j]);
		}
	}
 
	return global[k];
}