You are given the prices of stock for n number of days. every ith day tell the price of the stock on that day.find the maximum profit that you can make by buying and selling stock any number of times as you can't proceed with other transactions if you hold any transaction.
Example:
Input:
n = 7
prices = [1,2,3,4,5,6,7]
Output:
6
Explaination:
We can make the maximum profit by buying the stock on the first day and selling it on the last day.
Your Task:
You don't have to read input or print anything. Your task is to complete the function maximizeProfit() which takes the integer n and array prices and returns the maximum profit that can earn.
Expected Time Complexity: O(n)
Expected Space Complexity: O(n^{2})
NOTE: can you solve this in less space complexity?
Constraint:
1<=n<=10^{5}
1<=prices[i]<=10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM

Starter code: #User function Template for python3



class Solution:

    def maximumProfit(self, prices, n):

        #Code here

Solutions:
class Solution:

	def maximumProfit(self, prices, n):
		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]
					notsell = 0 + nex[0]
					profit = max(sellnow, notsell)
				curr[buy] = profit
			nex = curr
		return nex[1]


class Solution:

	def maximumProfit(self, prices, n):
		ans = 0
		prev = 0
		for i in range(1, n):
			if prices[i] > prices[prev]:
				ans += prices[i] - prices[prev]
			prev = i
		return ans


class Solution:

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


class Solution:

	def maximumProfit(self, prices, n):
		profit = 0
		for i in range(n - 1):
			x = prices[i + 1] - prices[i]
			if x < 0:
				continue
			profit += x
		if profit < 0:
			return 0
		return profit


class Solution:

	def maximumProfit(self, prices, n):
		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:
					profit = max(-prices[ind] + dp[ind + 1][0], dp[ind + 1][1])
				else:
					profit = max(prices[ind] + dp[ind + 1][1], dp[ind + 1][0])
				dp[ind][buy] = profit
		return dp[0][1]


class Solution:

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


class Solution:

	def maximumProfit(self, A, n):
		i = 0
		ans = 0
		while i < n:
			while i + 1 < n and A[i] >= A[i + 1]:
				i += 1
			l = A[i]
			while i + 1 < n and A[i] <= A[i + 1]:
				i += 1
			r = A[i]
			if l == r:
				return ans
			ans += r - l
			i += 1
		return ans


class Solution:

	def maximumProfit(self, prices, n):
		minm = prices[0]
		profit = 0
		for i in range(1, n):
			if prices[i] > minm:
				profit += prices[i] - minm
				minm = prices[i]
			else:
				minm = prices[i]
		return profit


class Solution:

	def maximumProfit(self, prices, n):
		n = len(prices)
		dp = [[0 for _ in range(3)] for _ in range(n + 1)]
		for i in range(n - 1, -1, -1):
			for buy in range(2):
				if buy == 1:
					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], dp[i + 1][0])
		return dp[0][1]


class Solution:

	def maximumProfit(self, prices, n):
		(profit, A) = (0, prices)
		for i in range(n - 1):
			if A[i + 1] > A[i]:
				profit += A[i + 1] - A[i]
		return profit


class Solution:

	def maximumProfit(self, prices, n):
		dp = [[0 for i in range(2)] for i in range(n + 1)]
		ans = 0
		for j in range(1, len(prices)):
			if prices[j - 1] < prices[j]:
				ans += prices[j] - prices[j - 1]
		return ans


class Solution:

	def maximumProfit(self, prices, n):
		max_profit = 0
		for i in range(1, n):
			if prices[i] > prices[i - 1]:
				max_profit += prices[i] - prices[i - 1]
		return max_profit


class Solution:

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


class Solution:

	def maximumProfit(self, arr, n):
		dp = [[0 for i in range(2)] for j in range(n + 1)]
		dp[n][0] = 0
		dp[n][1] = 0
		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]
					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):
		profit = 0
		i = 1
		while i < n:
			buy = i - 1
			while i < n and prices[i] > prices[i - 1]:
				i += 1
			sell = i - 1
			profit += prices[sell] - prices[buy]
			i += 1
		return profit


class Solution:

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


class Solution:

	def maximumProfit(self, arr, n):
		i = 0
		final_ans = []
		while i < n - 1:
			if arr[i] <= arr[i + 1]:
				ans = []
				ans.append(arr[i])
				while i < n - 1 and arr[i] <= arr[i + 1]:
					i += 1
				ans.append(arr[i])
				final_ans.append(ans)
			else:
				i += 1
		answer = 0
		for res in final_ans:
			answer = answer + (res[1] - res[0])
		return answer


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


import sys
sys.setrecursionlimit(10 ** 8)
mod = 10 ** 9

class Solution:

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


class Solution:

	def maximumProfit(self, arr, n):
		(l, r) = (0, 1)
		total = 0
		prev = 0
		while r < n:
			curr = arr[r] - arr[l]
			if curr > prev:
				prev = curr
				if r == n - 1:
					total += prev
			elif curr < prev:
				total += prev
				prev = 0
				l = r
			r += 1
		return total


class Solution:

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


import sys

class Solution:

	def maximumProfit(self, prices, n):
		minI = 0
		res = []
		for i in range(n):
			if i == n - 1 or (i < n - 1 and prices[i] > prices[i + 1]):
				if i != minI:
					res.append([minI, i])
				minI = i + 1
		prof = 0
		for p in res:
			prof += prices[p[1]] - prices[p[0]]
		return prof


class Solution:

	def maximumProfit(self, prices, n):
		total_profit = 0
		buy = 0
		sell = 0
		for i in range(1, n):
			if prices[i] >= prices[i - 1]:
				sell += 1
			else:
				total_profit += prices[sell] - prices[buy]
				buy = i
				sell = i
		total_profit += prices[sell] - prices[buy]
		return total_profit