首页 > 代码库 > [LeetCOde][Java] Best Time to Buy and Sell Stock III
[LeetCOde][Java] Best Time to Buy and Sell Stock III
题目:
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
算法分析:
利用通用的算法《Best Time to Buy and Sell Stock
IV》 将k变为2 就ok
AC代码:
<span style="font-family:Microsoft YaHei;font-size:12px;">public class Solution { public int maxProfit(int[] prices) { return maxProfit(2,prices); } public int maxProfit(int k, int[] prices) { if(prices==null || prices.length==0) return 0; if(k>prices.length)//k次数大于天数时,转化为问题《Best Time to Buy and Sell Stock II》--无限次交易的情景 { if(prices==null) return 0; int res=0; for(int i=0;i<prices.length-1;i++) { int degit=prices[i+1]-prices[i]; if(degit>0) res+=degit; } return res; } /* 定义维护量: global[i][j]:在到达第i天时最多可进行j次交易的最大利润。此为全局最优 local[i][j]:在到达第i天时最多可进行j次交易而且最后一次交易在最后一天卖出的最大利润。此为局部最优 定义递推式: global[i][j]=max(global[i-1][j],local[i][j]);即第i天没有交易,和第i天有交易 local[i][j]=max(global[i-1][j-1]+max(diff,0),local[i-1][j]+diff) diff=price[i]-price[i-1]; */ int[][] global=new int[prices.length][k+1]; int[][] local=new int[prices.length][k+1]; for(int i=0;i<prices.length-1;i++) { int diff=prices[i+1]-prices[i]; for(int j=0;j<=k-1;j++) { local[i+1][j+1]=Math.max(global[i][j]+Math.max(diff,0),local[i][j+1]+diff); global[i+1][j+1]=Math.max(global[i][j+1],local[i+1][j+1]); } } return global[prices.length-1][k]; } }</span>
[LeetCOde][Java] Best Time to Buy and Sell Stock III
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。