首页 > 代码库 > Problem Best Time to Buy and Sell Stock III
Problem Best Time to Buy and Sell Stock III
Problem Description:
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:
1 public int maxProfit(int[] prices) { 2 if (prices.length <= 1) return 0; 3 4 int[] profit = new int[prices.length + 1]; 5 int maxProfit = 0; 6 int low = prices[0]; 7 for (int i = 1; i < prices.length; i++) { 8 if (low > prices[i]) low = prices[i]; 9 maxProfit = Math.max(maxProfit, prices[i] - low);10 profit[i] = maxProfit;11 }12 maxProfit = 0;13 int st = prices[prices.length - 1];14 for (int i = prices.length - 2; i >= 0; i--) {15 maxProfit = Math.max(maxProfit, profit[i] + st - prices[i]);16 st = Math.max(st, prices[i]);17 }18 19 return maxProfit;20 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。