程序人生|漫画：程序教你寻找股票买入卖出的最佳时机（动态规划）( 五 )

本文插图

本文插图

本文插图

本文插图
//最大买卖次数 private static int MAX_DEAL_TIMES = 2; public static int maxProfitFor2TimeV2(int[] prices) { if(prices== || prices.length==0) { return 0; } //表格的最大行数 int n = prices.length; //表格的最大列数 int m = MAX_DEAL_TIMES*2+1; //使用一维数组记录数据 int resultTable = new int[m]; //填充初始状态 resultTable[1] = -prices[0]; resultTable[3] = -prices[0]; //自底向上，填充数据 for(int i=1;i for(int j=1;j if((j&1) == 1){ resultTable[j] = Math.max(resultTable[j], resultTable[j-1]-prices[i]); }else { resultTable[j] = Math.max(resultTable[j], resultTable[j-1]+prices[i]); } } } //返回最终结果 return resultTable[m-1]; }在这段代码中， resultTable从二维数组简化成了一维数组。由于最大买卖次数是常量，所以算法的时间复杂度也从O（n）降低到了O（1）。

本文插图

本文插图

本文插图
public static int maxProfitForKTime(int[] prices, int k) { if(prices== || prices.length==0) { return 0; } //表格的最大行数 int n = prices.length; //表格的最大列数 int m = k*2+1; //使用一维数组记录数据 int resultTable = new int[m]; //填充初始状态 resultTable[1] = -prices[0]; resultTable[3] = -prices[0]; //自底向上，填充数据 for(int i=1;i for(int j=1;j if((j&1) == 1){ resultTable[j] = Math.max(resultTable[j], resultTable[j-1]-prices[i]); }else { resultTable[j] = Math.max(resultTable[j], resultTable[j-1]+prices[i]); } } } //返回最终结果 return resultTable[m-1]; }

本文插图

本文插图