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

Source: leetcode | Difficulty: EASY
Tags: Dynamic programming

Data structures

Greedy algorithms

Starter code: class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        

Solutions:
class Solution:

	def maxProfit(self, prices):
		profits = 0
		ln = len(prices)
		if not ln:
			return 0
		elif ln == 2:
			return prices[1] - prices[0] if prices[1] > prices[0] else 0
		lastPrice = prices[0]
		for price in prices:
			if lastPrice < price:
				profits += price - lastPrice
			lastPrice = price
		return profits


class Solution:

	def maxProfit(self, prices):
		maxprofit = 0
		for i in range(1, len(prices)):
			if prices[i] > prices[i - 1]:
				maxprofit += prices[i] - prices[i - 1]
		return maxprofit


class Solution:

	def maxProfit(self, prices):
		if not prices or len(prices) == 1:
			return 0
		ans = 0
		for i in range(len(prices) - 1, 0, -1):
			prices[i] -= prices[i - 1]
		for i in range(1, len(prices), 1):
			if prices[i] > 0:
				ans += prices[i]
		return ans


class Solution:

	def maxProfit(self, prices):
		prof = 0
		for j in range(len(prices) - 1):
			if prices[j + 1] > prices[j]:
				prof += prices[j + 1] - prices[j]
		return prof


class Solution:

	def maxProfit(self, prices):
		cum = 0
		for iprice in range(1, len(prices)):
			if prices[iprice - 1] < prices[iprice]:
				cum += prices[iprice] - prices[iprice - 1]
		return cum


class Solution:

	def maxProfit(self, prices):
		if len(prices) < 2:
			return 0
		max1 = 0
		for i in range(1, len(prices)):
			print(max1)
			max1 += max(0, prices[i] - prices[i - 1])
		return max1


class Solution:

	def maxProfit(self, prices):
		return sum((max(prices[i] - prices[i - 1], 0) for i in range(1, len(prices))))


class Solution:

	def maxProfit(self, prices):
		if len(prices) == 0:
			return 0
		hold = -prices[0]
		sell = 0
		for i in range(1, len(prices)):
			sell = max(sell, hold + prices[i])
			hold = max(hold, sell - prices[i])
		return max(hold, sell)


class Solution:

	def maxProfit(self, prices):
		if len(prices) < 2:
			return 0
		buy = prices[0]
		sell = -1
		profit = 0
		i = 1
		while i < len(prices):
			if buy >= prices[i]:
				if sell > -1:
					profit += sell - buy
					sell = -1
					buy = prices[i]
				else:
					buy = prices[i]
			if prices[i] > buy:
				if prices[i] > sell:
					sell = prices[i]
				else:
					profit += sell - buy
					sell = -1
					buy = prices[i]
			i += 1
		if sell > -1:
			profit += sell - buy
		return profit


class Solution:

	def maxProfit(self, prices):
		p = 0
		for i in range(1, len(prices)):
			profit = prices[i] - prices[i - 1]
			if profit > 0:
				p += profit
		return p


class Solution:

	def maxProfit(self, prices):
		if len(prices) < 2:
			return 0
		profit = [0] * (len(prices) + 1)
		pro_minus_pri = profit[0] - prices[0]
		for i in range(2, len(prices) + 1):
			profit[i] = max(profit[i - 1], prices[i - 1] + pro_minus_pri)
			pro_minus_pri = max(profit[i - 1] - prices[i - 1], pro_minus_pri)
		return profit[len(prices)]