首页 > 代码库 > [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).
Solution:
从左至右，从右至左，分别扫一遍，得到在该天以前，以后分别进行一次操作的利润 l2r[i] , r2l[i]。
1 public class Solution { 2 public int maxProfit(int[] prices) { 3 int N = prices.length; 4 if (N < 2) 5 return 0; 6 int[] l2r = new int[N]; 7 int[] r2l = new int[N]; 8 int minn = prices[0]; 9 l2r[0] = 0;10 for (int i = 1; i < N; ++i) {11 minn = Math.min(minn, prices[i]);12 l2r[i] = Math.max(l2r[i - 1], prices[i] - minn);13 }14 r2l[N - 1] = 0;15 int maxx = prices[N - 1];16 for(int i=N-2;i>=0;--i){17 maxx=Math.max(maxx, prices[i]);18 r2l[i]=Math.max(r2l[i+1], maxx-prices[i]);19 }20 int result=l2r[N-1];21 for(int i=0;i<N-1;i++){22 result=Math.max(result, l2r[i]+r2l[i+1]);23 }24 return result;25 }26 }
需要注意的是：
1： 存在只进行一次操作，记得到最优解的可能（题目：You may complete at most two transactions.）。要对result赋初值。
int result=l2r[N-1];
2： 你不能当天进行两次操作，今天卖出了，明天才能买进。
result=Math.max(result, l2r[i]+r2l[i+1]);[Leetcode] Best Time to Buy and Sell Stock III
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。