首页 > 代码库 > 【leetcode刷题笔记】Best Time to Buy and Sell Stock III
【leetcode刷题笔记】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).
题解:DP
从前往后扫描一遍数组,用LeftToRight[i]记录(0,i)得到的最大利润;
从后往前扫描一遍数组,用RightToLeft[i]记录(i,n-1)得到的最大利润;
最终的最大利润是max(LeftToRight[i]+RightToLeft[i])。
举个例子,如果prices = {1,2,3,2,5,7},对应的
LeftToRight = {0,1,2,2,4,6}
RightToLeft = {6,5,5,5,2,0}
最终的最大利润就是2+5=7。表示在0~2(或0~3)这个区间取得利润2,并且在2~5(或者3~5)这个区间取得利润5,最终得到利润7.
代码如下:
1 public class Solution { 2 public int maxProfit(int[] prices) { 3 if(prices == null || prices.length == 0) 4 return 0; 5 6 int[] LeftToRight = new int[prices.length]; 7 int[] RightToLeft = new int[prices.length]; 8 9 int minimal = prices[0];10 LeftToRight[0] = 0;11 for(int i = 1;i < prices.length;i++){12 minimal = Math.min(minimal, prices[i]);13 LeftToRight[i] = Math.max(LeftToRight[i-1], prices[i]-minimal);14 }15 16 int profit = 0;17 //From Right to left18 RightToLeft[prices.length-1] = 0;19 int maximal = prices[prices.length-1];20 for(int i = prices.length-2;i >= 0;i--){21 maximal = Math.max(prices[i], maximal);22 RightToLeft[i]= Math.max(RightToLeft[i+1], maximal-prices[i]);23 profit = Math.max(profit, LeftToRight[i] + RightToLeft[i] );24 }25 26 return Math.max(profit, LeftToRight[0]+RightToLeft[0]);27 }28 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。