You are given an array prices where prices[i] is the price of a given stock on the i^{th} day, and an integer fee representing a transaction fee.
Find the maximum profit you can achieve. You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction.
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Example:
Input:
n = 6
prices = [1,3,2,8,4,9]
fee = 2
Output:
8
Explanation:
The maximum profit can be achieved by:
- Buying at prices[0] = 1
- Selling at prices[3] = 8
- Buying at prices[4] = 4
- Selling at prices[5] = 9
The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
Your Task:
You don't have to read input or print anything. Your task is to complete the function maximumProfit() which takes the integer n and array prices and transaction fee and returns the maximum profit that can earn.
Expected Time Complexity: O(n)
Expected Space Complexity: O(1)
Constraint:
1 <= n <= 5*10^{4}
1 <= prices[i] < 5 * 10^{4 }
0 <= fee < 5 * 10^{4}

Source: geeksforgeeks | Difficulty: MEDIUM

Starter code: #User function Template for python3



class Solution:

    def maximumProfit(self, prices, n, fee):

        #Code here

Solutions:
class Solution:

	def maximumProfit(self, prices, n, fee):
		n = len(prices)
		curr = [0 for i in range(2)]
		nex = [0 for i in range(2)]
		profit = 0
		for ind in range(n - 1, -1, -1):
			for buy in range(0, 2):
				if buy:
					buynow = -prices[ind] + nex[0]
					notbuy = 0 + nex[1]
					profit = max(buynow, notbuy)
				else:
					sellnow = prices[ind] + nex[1] - fee
					notsell = 0 + nex[0]
					profit = max(sellnow, notsell)
				curr[buy] = profit
			nex = curr
		return nex[1]


class Solution:

	def maximumProfit(self, prices, n, fee):
		a = 0
		b = -prices[0] - fee
		for i in range(1, n):
			(a, b) = (max(prices[i] + b, a), max(b, a - prices[i] - fee))
		return a


class Solution:

	def maximumProfit(self, prices, n, fee):
		dp = [0] * n
		dp2 = [0] * n
		dp[0] = 0
		dp2[0] = -prices[0] - fee
		for i in range(1, n):
			dp[i] = max(prices[i] + dp2[i - 1], dp[i - 1])
			dp2[i] = max(dp2[i - 1], dp[i - 1] - prices[i] - fee)
		return dp[n - 1]


class Solution:

	def maximumProfit(self, prices, n, fee):
		(buy, sell) = (-10 ** 9, 0)
		for p in prices:
			tmp = buy
			buy = max(buy, sell - p)
			sell = max(sell, tmp + p - fee)
		return sell


class Solution:

	def maximumProfit(self, prices, n, fee):
		ahead = curr = [0] * 2
		for ind in range(n - 1, -1, -1):
			for buy in range(2):
				if buy:
					curr[buy] = max(-prices[ind] + ahead[0], ahead[1])
				else:
					curr[buy] = max(prices[ind] - fee + ahead[1], ahead[0])
			ahead = curr
		return ahead[1]


class Solution:

	def maximumProfit(self, prices, n, fee):
		dp = [[-1 for i in range(2)] for j in range(n + 1)]
		dp[n][0] = dp[n][1] = 0
		for ind in range(n - 1, -1, -1):
			for buy in range(2):
				if buy:
					dp[ind][buy] = max(-prices[ind] + dp[ind + 1][0], dp[ind + 1][1])
				else:
					dp[ind][buy] = max(prices[ind] - fee + dp[ind + 1][1], dp[ind + 1][0])
		return dp[0][1]


class Solution:

	def maximumProfit(self, prices, n, fee):
		n = len(prices)
		dp = [[0 for _ in range(2)] for _ in range(n + 1)]
		for i in range(n - 1, -1, -1):
			for buy in range(2):
				if buy:
					dp[i][buy] = max(-prices[i] + dp[i + 1][0], dp[i + 1][1])
				else:
					dp[i][buy] = max(prices[i] + dp[i + 1][1] - fee, dp[i + 1][0])
		return dp[0][1]


class Solution:

	def maximumProfit(self, prices, n, fee):
		ahead1 = [0 for i in range(2)]
		for ind in range(n - 1, -1, -1):
			curr = [0 for i in range(2)]
			curr[1] = max(-prices[ind] + ahead1[0], ahead1[1])
			curr[0] = max(prices[ind] - fee + ahead1[1], ahead1[0])
			ahead1 = curr
		return ahead1[1]


class Solution:

	def maximumProfit(self, arr, n, fee):
		dp = [[0 for i in range(2)] for j in range(n + 1)]
		for idx in range(n - 1, -1, -1):
			for buy in range(2):
				profit = 0
				if buy:
					p = -arr[idx] + dp[idx + 1][0]
					np = 0 + dp[idx + 1][1]
					profit = max(profit, max(p, np))
				else:
					s = arr[idx] + dp[idx + 1][1] - fee
					ns = 0 + dp[idx + 1][0]
					profit = max(profit, max(s, ns))
				dp[idx][buy] = profit
		return dp[0][1]


class Solution:

	def maximumProfit(self, prices, n, fee):
		dp = [[0] * 2 for _ in range(n + 1)]
		for i in range(n - 1, -1, -1):
			for j in range(2):
				if j == 0:
					dp[i][j] = max(dp[i + 1][0], dp[i + 1][1] - prices[i])
				if j == 1:
					dp[i][j] = max(dp[i + 1][1], dp[i + 1][0] + prices[i] - fee)
		return dp[0][0]


class Solution:

	def maximumProfit(self, prices, n, fee):
		next = [0] * 2
		for i in range(n - 1, -1, -1):
			curr = [0] * 2
			for buy in range(2):
				if buy:
					Buy = next[0] - prices[i]
					notBuy = next[1]
					profit = max(Buy, notBuy)
				else:
					sell = next[1] + prices[i] - fee
					notSell = next[0]
					profit = max(sell, notSell)
				curr[buy] = profit
			next = curr
		return next[1]


class Solution:

	def maximumProfit(self, arr, n, fee):
		dp = [[0 for j in range(0, 2)] for i in range(0, n + 1)]
		for i in range(n - 1, -1, -1):
			for bought in range(0, 2):
				profit = 0
				if bought == 0:
					buy = -arr[i] + dp[i + 1][1]
					notbuy = dp[i + 1][0]
					profit = max(buy, notbuy)
				else:
					sell = arr[i] - fee + dp[i + 1][0]
					notsell = dp[i + 1][1]
					profit = max(sell, notsell)
				dp[i][bought] = profit
		return dp[0][0]


class Solution:

	def maximumProfit(self, A, n, fee):
		dp = [[0 for _ in range(2)] for _ in range(n + 1)]
		for ind in range(n - 1, -1, -1):
			take = -A[ind] + dp[ind + 1][0]
			noTake = 0 + dp[ind + 1][1]
			dp[ind][1] = max(take, noTake)
			take = A[ind] + dp[ind + 1][1] - fee
			noTake = 0 + dp[ind + 1][0]
			dp[ind][0] = max(take, noTake)
		return dp[0][1]


class Solution:

	def maximumProfit(self, prices, n, fee):
		after = [0] * 2
		cur = [0] * 2
		for ind in range(n - 1, -1, -1):
			cur[1] = max(-1 * prices[ind] + after[0], after[1])
			cur[0] = max(prices[ind] - fee + after[1], after[0])
			after = list(cur)
		return after[1]


class Solution:

	def maximumProfit(self, prices, n, fee):
		dp = [[0] * 2 for i in range(n + 1)]
		for idx in range(n - 1, -1, -1):
			for buy in range(2):
				mProfit = 0
				if buy:
					mProfit = max(-prices[idx] - fee + dp[idx + 1][0], dp[idx + 1][1])
				else:
					mProfit = max(+prices[idx] + dp[idx + 1][1], dp[idx + 1][0])
				dp[idx][buy] = mProfit
		return dp[0][1]


class Solution:
	dp = [[]]

	def util(self, price, buy, idx, n, fee):
		if idx >= n:
			return 0
		if self.dp[idx][buy] != -1:
			return self.dp[idx][buy]
		profit = 0
		if buy:
			buyit = -price[idx] + self.util(price, 0, idx + 1, n, fee)
			dont_buyit = 0 + self.util(price, 1, idx + 1, n, fee)
			profit = max(buyit, dont_buyit)
		else:
			sellit = price[idx] + self.util(price, 1, idx + 1, n, fee) - fee
			dont_sellit = 0 + self.util(price, 0, idx + 1, n, fee)
			profit = max(sellit, dont_sellit)
		self.dp[idx][buy] = profit
		return self.dp[idx][buy]

	def maximumProfit(self, prices, n, fee):
		s0 = -prices[0]
		s1 = 0
		for price in prices:
			f0 = max(s0, s1 - price)
			f1 = max(s1, s0 + price - fee)
			(s0, s1) = (f0, f1)
		return s1