登录
  • #刷题

买卖‌‌‍‍‌‍‍‌‍‌‌‍‌‍‍‍‌‍‍‍‍‌‌‍‌‌‍‌‌‍‍‍股票最佳时机--- IV

xh_pku
2926
5
假定最大交易次数为k次,我们定义local[j]为在到达第i天时最多可进行j次交易并且最后一次交易在最后一天卖出的最大利润,此为局部最优。然后我们定义global[j]为在到达第i天时最多可进行j次交易的最大利润,此为全局最优。



transition equation:

diff = prices - prices;

local[j] = Max(global[j - 1] + diff, local[j] + diff);





global[j] = Max(global[j], local[j]);





代码如下:
/*[br][/br][br][/br] * j -- max # of transactions; i --- # of days;[br][/br][br][/br] *  local[i][j] -- profit achieved when selling at last day;[br][/br][br][/br] *  global[i][j] --- profit achieved at all situations;[br][/br][br][/br] *  transition equation:[br][/br][br][/br] *  	local[i][j] =  max(local[i][j], global[i][j - 1]) + diff;[br][/br][br][/br] *      (merge with previous transactions or NOT)[br][/br][br][/br] *      global[i][j] = max(local[i][j], global[i][j]);[br][/br][br][/br] */[br][/br][br][/br]public class SolutionIV {[br][/br][br][/br]    public int maxProfit(int k, int[] prices) {[br][br][/br]    	int N = prices.length;[br][/br][br][/br]    	if (k >= N)[br][/br][br][/br]    		return simpleMaxProfit(prices);[br][/br][br][/br]        int[] local = new int[k + 1], global = new int[k + 1];[br][/br][br][/br]        int[] prevLocal = new int[k + 1], prevGlobal = new int[k + 1];[br][/br][br][/br]        for (int i = 1; i < N; ++i) {[br][/br][br][/br]        	prevLocal = local; prevGlobal = global;[br][/br][br][/br]        	local = new int[k + 1]; global = new int[k + 1];[br][/br][br][/br]        	int diff = prices[i] - prices[i];[br][/br][br][/br]        	for (int j = 1; j <= k; ++j) {[br][/br][br][/br]        		local[j] = Math.max(prevGlobal[j - 1], prevLocal[j]) + diff;[br][/br][br][/br]        		global[j] = Math.max(local[j], prevGlobal[j]);[br][/br][br][/br]        	}[br][/br][br][/br]        }[br][/br][br][/br]        return global[k];[br][/br][br][/br]    }[br][/br][br][/br]    int simpleMaxProfit(int[] prices) {[br][br][/br]    	int N = prices.length;[br][/br][br][/br]    	if (N <= 1)[br][/br][br][/br]    		return 0;[br][/br][br][/br]    	int sum = 0;[br][/br][br][/br]    	for (int i = 1; i < N; i++) {[br][/br][br][/br]    		int diff = prices[i] - prices[i];[br][/br][br][/br]    		if (diff > 0)[br][/br][br][/br]    			sum += diff;[br][/br][br][/br]    	}[br][/br][br][/br]    	return sum;[br][/br][br][/br]    }[br][/br][br][/br]    public static void main(String[] args) {[br][br][/br]        SolutionIV sol = new SolutionIV();[br][/br][br][/br]        int[] nums = {4, 6, 1, 1, 4, 2, 5};[br][br][/br]        System.out.println(sol.maxProfit(2, nums));[br][/br][br][/br]    }[br][/br][br][/br]}[br][/br][br][/br][br][/br][br][/br][font][color][br][/br][br][/br][/color][/font][br][/br][br][/br][font][color][br][/br][br][/br][/color][/font][color][font][br][/br][br][/br][/font][/color][br][/br][br][/br][color][font][br][/br][br][/br][/font][/color][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]
5条回复
热度排序

发表回复