首页 > 代码库 > 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).
Analysis:
We calculate two things:1. from day 0 to day i, what the maximum profit we can get by performing only one transcation. 2. from any day i to the end, what the maximum profit we can get by performing one transcation. We then find out the maximum profit by adding them up for each day.
Solution:
1 public class Solution { 2 public int maxProfit(int[] prices) { 3 int len = prices.length; 4 if (len==0 || len==1) return 0; 5 6 int[] posProfit = new int[len]; 7 int[] negProfit = new int[len]; 8 9 int maxProfit = 0;10 int curProfit = 0;11 int minPrice = prices[0];12 for (int i=0;i<len;i++){13 if (minPrice>prices[i]) minPrice = prices[i];14 curProfit = prices[i]-minPrice;15 if (curProfit>maxProfit) maxProfit = curProfit;16 posProfit[i] = maxProfit;17 }18 19 maxProfit = 0;20 curProfit = 0;21 int maxPrice = prices[len-1];22 for (int i=len-1;i>=0;i--){23 if (maxPrice<prices[i]) maxPrice = prices[i];24 curProfit = maxPrice-prices[i];25 if (curProfit>maxProfit) maxProfit = curProfit;26 negProfit[i]=maxProfit;27 }28 29 int res = 0;30 for (int i=0;i<len;i++)31 if (res<posProfit[i]+negProfit[i]) res = posProfit[i]+negProfit[i];32 33 return res;34 }35 }
Leetcode-Best Time to Buy and Sell Stock III
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。