Solution to problem 122 “Best Time to Buy and Sell Stock II” from LeetCode.

Problem Statement

You are given an array where each i-th element is the price of a stock on day i. You need to create an algorithm that achieves maximum profit by buying and selling the stock.

Note: Imagine you have only one stock. Therefore, you can either sell it or buy it.

Example

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.
* Buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.

Total profit 4 + 3 = 7

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.

Input: [7,6,4,3,1]
Output: 0
Explanation:
Under these conditions buying is not profitable, so the result will be 0.

Solution

Finding Maxima and Minima

Algorithm idea:

Iterate through the array, finding local minimums and maximums. As soon as we find a local maximum - calculate the profit (difference between maximum and minimum).

func maxProfit(prices []int) int {
	if len(prices) < 2 {
		return 0
	}

	sum := 0

	localMin := prices[0]
	localMax := prices[0]
	vectorup := prices[1] > prices[0]

	for idx := 1; idx < len(prices); idx++ {
		if vectorup {
			if prices[idx] >= localMax {
				localMax = prices[idx]
			} else {
				sum += localMax - localMin
				vectorup = false
				localMin = prices[idx]

			}
		} else {
			if prices[idx] <= localMin {
				localMin = prices[idx]
			} else {
				vectorup = true
				localMax = prices[idx]
			}
		}
	}

	if vectorup && localMax > localMin {
		sum += localMax - localMin
	}

	return sum
}

Complexity

Memory: O(1) Operations: O(n)

Greedy Algorithm

Algorithm idea:

Every day check if the stock is more expensive than yesterday. If the stock is more expensive than yesterday - go back to yesterday – buy the stock, then return to the current day and sell the stock. This way, every day when the stock grows in price – profit will be added.

func maxProfit(prices []int) int {
	if len(prices) < 2 {
		return 0
	}
	sum := 0

	for idx := 1; idx < len(prices); idx++ {
		if prices[idx] > prices[idx-1] {
			sum += prices[idx] - prices[idx-1]
		}
	}

	return sum
}

Complexity

Memory: O(1) Operations: O(n)