Say you have an array prices 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 (i.e., buy one and sell one share of the stock multiple times).
Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).
Example 1:
Input: [7,1,5,3,6,4] Output: 7 Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4. Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Example 2:
Input: [1,2,3,4,5] Output: 4 Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4. Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.
Example 3:
Input: [7,6,4,3,1] Output: 0 Explanation: In this case, no transaction is done, i.e. max profit = 0.
Constraints:
1 <= prices.length <= 3 * 10 ^ 40 <= prices[i] <= 10 ^ 4
The description was taken from https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/.
#O(N) Time, O(1) Spaceclass Solution: def maxProfit(self, prices: List[int]) -> int: if len(prices) == 0: return 0 max_profit = 0 for i in range(1, len(prices)): if prices[i] > prices[i-1]: max_profit += prices[i] - prices[i-1] return max_profitThe maximum profit we would be able to gain is every profit.
If we iterate through each day and compare the stock price of the current day with the stock price of the previous day and we see that today it is higher, then we will choose to buy the stock on the previous day and sell it on the current day to collect each profit we can.
Let's start by checking if the length of our prices array is zero. If it is there is no profit to be had so we’ll return zero.
if len(prices) is 0: return 0
Otherwise, we’ll initialize our max profit to zero because in the worst case, we buy on the first day and the price just keeps dropping from there so we will gain no profit.
maxprofit = 0
We’ll then iterate through the prices array starting from the second day to compare each day with the day before.
for i in range(1, len(prices)):
If the price on the current day is higher then we’ll subtract the previous day’s price from the current day’s price then add the difference to the max profit variable. This is us buying yesterday and selling today. We will take that difference and add it to the max profit for the week.
if prices[i] > prices[i-1]: maxprofit += prices[i] - prices[i-1]
Once we have calculated the maximum possible profit, we will return its value.
return maxprofit