LC-0122 Medium LeetCode

122. Best Time to Buy and Sell Stock II

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 69% Topics: Array, Dynamic Programming, Greedy

Reading material

Arrays & Hashing 12 min 1-D Dynamic Programming 16 min Greedy 11 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(1)


class Solution(object):
    # @param prices, a list of integer
    # @return an integer
    def maxProfit(self, prices):
        profit = 0
        for i in xrange(len(prices) - 1):
            profit += max(0, prices[i + 1] - prices[i])
        return profit

    def maxProfit2(self, prices):
        return sum(map(lambda x: max(prices[x + 1] - prices[x], 0),
                       xrange(len(prices[:-1]))))

Solution from kamyu104/LeetCode-Solutions · MIT