Best Time To Buy Sell Stocks

Definition

Definition

Problem of finding the maximum profit from buying and selling stocks at the right times

Explanation

To find the best time to buy and sell stocks, start by initializing variables to track the minimum stock price and maximum profit. Then, go through each day's stock price, updating the minimum price encountered so far. Calculate the potential profit if selling at the current price and update the maximum profit if this exceeds the current maximum. Finally, return the maximum profit found

Guidance

Detailed Description

Say you have an array prices for which the i-th element is the price of a given stock on day i. 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.

Examples

Divide and Conquer

Complexity: Time: O(2n) Space: O(n)

Using a divide and conquer approach, we can exhaustively explore all buying and selling combinations to find the most profitable one. For instance, given an array of prices like [7, 6, 4, 3, 1], at each step, we decide whether to keep the money or buy/sell at the current price, recursively considering the remaining stocks.

Peak Valley

Complexity: Time: O(n) Space: O(1)

If we plot the prices array [7, 1, 5, 3, 6, 4] we may notice that the points of interest are the consecutive valleys and peaks

Accumulator

Complexity: Time: O(n) Space: O(1)

With prices array [1, 7, 2, 3, 6, 7, 6, 7] we may notice that we don't need to keep track of all the points of interest. Instead, we may simply add the price difference for all growing segments of the chart which eventually sums up to the highest possible profit

Tips

• ensure the algorithm handles edge cases like an empty list of stock prices
• emphasize efficiency to handle large datasets efficiently
• utilize dynamic programming to optimize time complexity

Practice

Practice

function maxProfit(prices):
  if prices is empty:
    return 0

  min_price = infinity
  max_profit = 0

  for price in prices:
    min_price = min(min_price, price)
    potential_profit = price - min_price
    max_profit = max(max_profit, potential_profit)

  return max_profit

Solution

package main

import (
	"math"
)

func maxProfitDC(prices []int) int {
	return maxProfitHelper(prices, 0, len(prices)-1)
}

func maxProfitHelper(prices []int, start, end int) int {
	if start >= end {
		return 0
	}

	mid := start + (end-start)/2

	leftProfit := maxProfitHelper(prices, start, mid)
	rightProfit := maxProfitHelper(prices, mid+1, end)
	crossProfit := maxCrossProfit(prices, start, mid, end)

	return max(leftProfit, max(rightProfit, crossProfit))
}

func maxCrossProfit(prices []int, start, mid, end int) int {
	leftMax := math.MinInt64
	rightMax := math.MinInt64

	leftSum := 0
	for i := mid; i >= start; i-- {
		leftSum += prices[i]
		leftMax = max(leftMax, leftSum)
	}

	rightSum := 0
	for i := mid + 1; i <= end; i++ {
		rightSum += prices[i]
		rightMax = max(rightMax, rightSum)
	}

	return leftMax + rightMax
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

public class Main {

  public int maxProfitDC(int[] prices) {
    return maxProfitHelper(prices, 0, prices.length - 1);
  }

  private int maxProfitHelper(int[] prices, int start, int end) {
    if (start >= end) {
      return 0;
    }

    int mid = start + (end - start) / 2;

    int leftProfit = maxProfitHelper(prices, start, mid);
    int rightProfit = maxProfitHelper(prices, mid + 1, end);
    int crossProfit = maxCrossProfit(prices, start, mid, end);

    return Math.max(leftProfit, Math.max(rightProfit, crossProfit));
  }

  private int maxCrossProfit(int[] prices, int start, int mid, int end) {
    int leftMax = Integer.MIN_VALUE;
    int rightMax = Integer.MIN_VALUE;

    int leftSum = 0;
    for (int i = mid; i >= start; i--) {
      leftSum += prices[i];
      leftMax = Math.max(leftMax, leftSum);
    }

    int rightSum = 0;
    for (int i = mid + 1; i <= end; i++) {
      rightSum += prices[i];
      rightMax = Math.max(rightMax, rightSum);
    }

    return leftMax + rightMax;
  }
}

function maxProfitDC(prices) {
  return maxProfitHelper(prices, 0, prices.length - 1);
}

function maxProfitHelper(prices, start, end) {
  if (start >= end) {
    return 0;
  }

  const mid = Math.floor((start + end) / 2);

  const leftProfit = maxProfitHelper(prices, start, mid);
  const rightProfit = maxProfitHelper(prices, mid + 1, end);
  const crossProfit = maxCrossProfit(prices, start, mid, end);

  return Math.max(leftProfit, rightProfit, crossProfit);
}

function maxCrossProfit(prices, start, mid, end) {
  let leftMax = -Infinity;
  let rightMax = -Infinity;

  let leftSum = 0;
  for (let i = mid; i >= start; i--) {
    leftSum += prices[i];
    leftMax = Math.max(leftMax, leftSum);
  }

  let rightSum = 0;
  for (let i = mid + 1; i <= end; i++) {
    rightSum += prices[i];
    rightMax = Math.max(rightMax, rightSum);
  }

  return leftMax + rightMax;
}

fun maxProfitDC(prices: IntArray): Int {
    return maxProfitHelper(prices, 0, prices.size - 1)
}

fun maxProfitHelper(prices: IntArray, start: Int, end: Int): Int {
    if (start >= end) return 0

    val mid = start + (end - start) / 2

    val leftProfit = maxProfitHelper(prices, start, mid)
    val rightProfit = maxProfitHelper(prices, mid + 1, end)
    val crossProfit = maxCrossProfit(prices, start, mid, end)

    return maxOf(leftProfit, rightProfit, crossProfit)
}

fun maxCrossProfit(prices: IntArray, start: Int, mid: Int, end: Int): Int {
    var leftMax = Int.MIN_VALUE
    var rightMax = Int.MIN_VALUE

    var leftSum = 0
    for (i in mid downTo start) {
        leftSum += prices[i]
        leftMax = maxOf(leftMax, leftSum)
    }

    var rightSum = 0
    for (i in mid + 1..end) {
        rightSum += prices[i]
        rightMax = maxOf(rightMax, rightSum)
    }

    return leftMax + rightMax
}

def maxProfitOnePass(prices):
    if not prices:
        return 0

    max_profit = 0
    min_price = prices[0]

    for price in prices:
        min_price = min(min_price, price)
        max_profit = max(max_profit, price - min_price)

    return max_profit

fn max_profit_one_pass(prices: Vec<i32>) -> i32 {
    if prices.is_empty() {
        return 0;
    }

    let mut max_profit = 0;
    let mut min_price = prices[0];

    for price in prices {
        min_price = min_price.min(price);
        max_profit = max_profit.max(price - min_price);
    }

    max_profit
}

function maxProfitOnePass(prices: number[]): number {
  if (prices.length === 0) return 0;

  let maxProfit = 0;
  let minPrice = prices[0];

  for (let i = 1; i < prices.length; i++) {
    minPrice = Math.min(minPrice, prices[i]);
    maxProfit = Math.max(maxProfit, prices[i] - minPrice);
  }

  return maxProfit;
}