首页 > 代码库 > LeetCode-Best Time to Buy and Sell Stock III[dp]
LeetCode-Best Time to Buy and Sell Stock III[dp]
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).
标签: Array Dynamic Programming
分析:动态规划,设left[i]表示0-i天的最大利润,right[j]表示j-n-1天的最大利润,所以状态方程为:
left[i]=max(left[i-1],prices[i]-minleft); minleft表示0-i天的最低价
right[j]=max(right[j+1],maxright-prices[j]); maxright表示j-n-1天的最高价;
由于只可以买卖两次,并且在第二次买进是必须把第一次的卖掉,所以最大利润为max(left[i]+right[i]);
参考代码:
public class Solution { public int maxProfit(int[] prices) { int len=prices.length; if(len<2) return 0; int left[]=new int[len]; int right[]=new int[len]; int minleft=prices[0]; left[0]=0; for(int i=1;i<len;i++){ minleft=Math.min(minleft, prices[i]); left[i]=Math.max(left[i-1], prices[i]-minleft); } int maxright=prices[len-1]; right[len-1]=0; for(int j=len-2;j>=0;j--){ maxright=Math.max(maxright, prices[j]); right[j]=Math.max(right[j+1], maxright-prices[j]); } int maxProfit=left[0]+right[0]; for(int i=0;i<len;i++){ maxProfit=Math.max(maxProfit, left[i]+right[i]); } return maxProfit; } }
LeetCode-Best Time to Buy and Sell Stock III[dp]
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。