Question source

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).

0. Problem-solving ideas

Three ways to solve the problem: DFS, greedy algorithm and DP

1. Greedy algorithm

A greedy algorithm is a way which always choosing the best option for the current situation when solving the problem.

It requires one nested for loop and during each step, we check whether the next price is larger than the current price. If yes, we save the difference as the accumulate profit and add up to the previous profit. In the end of the loop, we can return the sum of the accumulate profits.

Complexity

  • Time complexity: O(n)

  • Space complexity:

Code

Code file

1
2
3
4
5
6
7
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0
        for i, element in enumerate(prices):
            if i<len(prices)-1 and element<prices[i+1]:
                profit = profit + prices[i+1] - element
        return profit

Summary

Greedy algorithm -
Runtime 60 ms, faster than 64.23% of Python3 online submissions -
Memory Usage 15.1 MB, less than 28.30% of Python3 online submissions -