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 as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again)
To avoid multiple simultaneous transactions, we consider buying the stock on dayi and selling it on day i+1 . If this brings in profit, i.e. price[i]<price[i+1] , we do it. If that is the case, Otherwise, we are safe to move to the next day, since we can buy the stock at a price not greater than that on day i .
To avoid multiple simultaneous transactions, we consider buying the stock on day
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0)
return 0;
int maximumProfit = 0; // Maximum profit up to now
// If buying the stock on day i and selling it on day i+1 brings in profit, do it.
// The only possible scenario that withdraws it is that buying on day i+1 and selling
// it on day i+2 also brings in profit. In that case it is equivalent to buying it
// on day i and selling it on day i+2
for (int i = 0; i < prices.length-1; i++)
maximumProfit += Math.max(prices[i+1]-prices[i], 0);
return maximumProfit;
}
Read full article from LeetCode - Best Time to Buy and Sell Stock II | Darren's Blog
No comments:
Post a Comment