Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:


Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
             Not 7-1 = 6, as selling price needs to be larger than buying price.


Example 2:


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

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

Solutions:
class Solution:

	def maxProfit(self, prices):
		n = len(prices)
		if n <= 1:
			return 0
		else:
			minprice = prices[0]
			res = 0
			for i in range(1, n):
				if prices[i] - minprice > res:
					res = prices[i] - minprice
				if prices[i] < minprice:
					minprice = prices[i]
			return res


class Solution:

	def maxProfit(self, prices):
		hold = float('inf')
		result = 0
		for p in prices:
			if p > hold:
				result = max(result, p - hold)
			hold = min(hold, p)
		return result


class Solution:

	def maxProfit(self, prices):
		if not prices:
			return 0
		(mincur, maxcur) = (prices[0], 0)
		for index in range(len(prices)):
			mincur = min(prices[index], mincur)
			maxcur = max(prices[index] - mincur, maxcur)
		return maxcur


class Solution:

	def maxProfit(self, prices):
		if len(prices) < 2:
			return 0
		max_profit = 0
		min_before = prices[0]
		for i in prices:
			min_before = min(i, min_before)
			max_profit = max(max_profit, i - min_before)
		return max_profit


class Solution:

	def maxProfit(self, prices):
		profit = 0
		buy = prices[0] if prices else None
		for price in prices:
			buy = min(buy, price)
			profit = max(profit, price - buy)
		return profit


class Solution:

	def maxProfit(self, prices):
		curr_min = float('inf')
		max_profit = 0
		for price in prices:
			curr_min = min(curr_min, price)
			profit = price - curr_min
			max_profit = max(max_profit, profit)
		return max_profit


class Solution:

	def maxProfit1(self, prices):
		if not prices:
			return 0
		(mincur, maxcur) = (prices[0], 0)
		for index in range(len(prices)):
			mincur = min(prices[index], mincur)
			maxcur = max(prices[index] - mincur, maxcur)
		return maxcur

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


class Solution:

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


class Solution:

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


class Solution:

	def maxProfit(self, prices):
		n = len(prices)
		return self.count_profit(prices, 0, n - 1)

	def count_profit(self, prices, left, right):
		if left >= right:
			return 0
		if right - left == 1:
			profit = prices[right] - prices[left]
			if profit < 0:
				profit = 0
			return profit
		mid = (left + right) // 2
		pro_left = self.count_profit(prices, left, mid)
		pro_right = self.count_profit(prices, mid + 1, right)
		pro_mid = 0
		i = min(prices[left:mid + 1])
		j = max(prices[mid + 1:right + 1])
		pro_mid = j - i
		profit = max(pro_left, pro_mid, pro_right)
		if profit < 0:
			profit = 0
		return profit


class Solution:

	def maxProfit(self, prices):
		if not prices:
			return 0
		min_price = prices[0]
		max_profit = 0
		for i in prices:
			if i < min_price:
				min_price = i
			elif max_profit < i - min_price:
				max_profit = i - min_price
		return max_profit


class Solution:

	def maxProfit(self, prices):
		if not prices:
			return 0
		min_val = prices[0]
		profit = 0
		for i in range(1, len(prices)):
			if profit < prices[i] - min_val:
				profit = prices[i] - min_val
			if prices[i] < min_val:
				min_val = prices[i]
		return profit