{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "f468b97b-3055-4f33-bde5-9995389d3c95",
   "metadata": {},
   "source": [
    "# Implementation of single-sell profit problem\n",
    "\n",
    "We start by defining a small list of prices, and then defining the brute-force solution, which returns a tuple of `(buy_index, sell_index, profit)`. We see that the best solution is to buy on day 4 for 1 dollar, then sell on day 5 for 9 dollars."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "201b2b04-4d11-4847-bf9e-b9ad9228dc96",
   "metadata": {},
   "outputs": [],
   "source": [
    "all_prices = [10, 5, 8, 12, 1, 9, 3, 7]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "93473e66-05a7-49aa-a7af-2213e9a4b1c7",
   "metadata": {},
   "outputs": [],
   "source": [
    "def brute_force(prices):\n",
    "    best = (0, 1, prices[1]-prices[0])\n",
    "    for i in range(len(prices)-1):\n",
    "        for j in range(i+1, len(prices)):\n",
    "            if prices[j]-prices[i] > best[2]:\n",
    "                best = (i, j, prices[j]-prices[i])\n",
    "    return best"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "a50e74e2-fe64-47d2-b83e-ef50fba8da1b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[10, 5, 8, 12, 1, 9, 3, 7]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(4, 5, 8)"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print(all_prices)\n",
    "brute_force(all_prices)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ef2d8d50-fece-4434-b81d-df63605f0974",
   "metadata": {},
   "source": [
    "Now we define the divide-and-conquer solution. Here's a textual description of the code.\n",
    "\n",
    "**Base Cases**\n",
    "- For lists of length 2, we have no choice buy to buy on the first day and sell on the second.\n",
    "- For lists of length 3, we have three choices - we return the one with the largest profit.\n",
    "\n",
    "**Divide**\n",
    "- We split the list into two lists, `left` and `right`, and call the function recursively on each half\n",
    "- `left_best` now contains the best buy-sell indices if we were limited to just the left half. Same with `right_best`\n",
    "\n",
    "**Combine**\n",
    "- In our larger array, the best choice is one of:\n",
    "  1. The solution from the left half\n",
    "  2. The solution from the right half (with indices adjusted to be correct - the index `i` in `right` is index `i+len(left)` in the full array `prices`)\n",
    "  3. The solution that is buying from the cheapest day in `left` and the most expensive day in `right`\n",
    "- We return the solution that is best of those three.\n",
    "\n",
    "We run it on our list, and see we get the same answer."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "6f24892d-cb0e-4d09-bb65-e8835133a8ab",
   "metadata": {},
   "outputs": [],
   "source": [
    "def max_profit(prices):\n",
    "    if len(prices)==2:\n",
    "        return (0, 1, prices[1]-prices[0])\n",
    "    if len(prices)==3:\n",
    "        choices = [ (0, 1, prices[1]-prices[0]), # buy on day 0, sell on day 1\n",
    "                    (0, 2, prices[2]-prices[0]), # buy on day 0, sell on day 2\n",
    "                    (1, 2, prices[2]-prices[1]) ]# buy on day 1, sell on day 2\n",
    "        return max(choices, key=lambda x:x[2])\n",
    "\n",
    "    mid = len(prices)//2\n",
    "    left = prices[:mid]\n",
    "    right = prices[mid:]\n",
    "\n",
    "    left_best = max_profit(left)\n",
    "    right_best = max_profit(right)\n",
    "\n",
    "    right_max = max(right)\n",
    "    right_max_index = right.index(right_max)+len(left)\n",
    "\n",
    "    left_min = min(left)\n",
    "    left_min_index = left.index(left_min)\n",
    "\n",
    "    choices = [left_best, (right_best[0]+len(left), right_best[1]+len(left), right_best[2]), (left_min_index, right_max_index, right_max-left_min)]\n",
    "    return max(choices, key=lambda x:x[2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "510aa1a7-469f-40dd-8aec-dfcb25ef882b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[10, 5, 8, 12, 1, 9, 3, 7]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(4, 5, 8)"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print(all_prices)\n",
    "max_profit(all_prices)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "29f8ebaa-ad20-4348-837e-084aeaef7589",
   "metadata": {},
   "source": [
    "We know the brute-force is $O(n^2)$ and the D&C is $O(n\\log(n))$. What does this mean practically? We see that even with this small list, the `max_profit` is noticeably faster than `brute_force`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "f77d06ce-899f-4a8b-8721-0c2d8cfd3c16",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(4, 5, 8)\n",
      "  0.00028204917907714844\n",
      "(4, 5, 8)\n",
      "  0.00011539459228515625\n"
     ]
    }
   ],
   "source": [
    "import time\n",
    "\n",
    "start = time.time()\n",
    "print(brute_force(all_prices))\n",
    "end = time.time()\n",
    "print(f'  {end-start}')\n",
    "\n",
    "start = time.time()\n",
    "print(max_profit(all_prices))\n",
    "end = time.time()\n",
    "print(f'  {end-start}')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5893f43f-7b7b-4d79-b6b0-37ed9e0a18e9",
   "metadata": {},
   "source": [
    "We now make a much bigger list, of size 20000. The difference in speed is even more pronounced (as we would expect). D&C is much faster."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "253f9bb2-c0c4-49c6-9d3a-4d1f60a726a1",
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "all_prices = [random.randint(1,10000) for _ in range(20000)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "862b4c12-137f-4a9c-a5c7-6876b1e45157",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(8043, 8562, 9997)\n",
      "  8.728413820266724\n",
      "(8043, 8562, 9997)\n",
      "  0.009593725204467773\n"
     ]
    }
   ],
   "source": [
    "import time\n",
    "\n",
    "start = time.time()\n",
    "print(brute_force(all_prices))\n",
    "end = time.time()\n",
    "print(f'  {end-start}')\n",
    "\n",
    "start = time.time()\n",
    "print(max_profit(all_prices))\n",
    "end = time.time()\n",
    "print(f'  {end-start}')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "82a65c58-79d9-4e21-86a1-1b113fc30355",
   "metadata": {},
   "source": [
    "**Greedy solution**\n",
    "\n",
    "There's actually a greedy solution to this problem, too, which is even faster ($O(n)$). The core idea is, what if I sold today? By tracking the minimum price seen so far, and the best profit achieved so far, we can iterate once through the list, and come up with an optimal solution even faster."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "914b2d14-212f-44c2-b70e-504f747aa198",
   "metadata": {},
   "outputs": [],
   "source": [
    "def greedy_profit(prices):\n",
    "    min_buy_price = prices[0]\n",
    "    min_buy_index = 0\n",
    "    max_profit = 0\n",
    "    \n",
    "    buy_index = 0\n",
    "    sell_index = 0\n",
    "\n",
    "    for i in range(1, len(prices)):\n",
    "        current_price = prices[i]\n",
    "        \n",
    "        potential_profit = current_price - min_buy_price\n",
    "        \n",
    "        if potential_profit > max_profit:\n",
    "            max_profit = potential_profit\n",
    "            buy_index = min_buy_index\n",
    "            sell_index = i\n",
    "\n",
    "        if current_price < min_buy_price:\n",
    "            min_buy_price = current_price\n",
    "            min_buy_index = i\n",
    "            \n",
    "    return buy_index, sell_index, max_profit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "b9220a5b-c06e-4599-8f1d-72d1cb5be304",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(8043, 8562, 9997)\n",
      "  7.878710985183716\n",
      "(8043, 8562, 9997)\n",
      "  0.009667396545410156\n",
      "(8043, 8562, 9997)\n",
      "  0.001009225845336914\n"
     ]
    }
   ],
   "source": [
    "import time\n",
    "\n",
    "start = time.time()\n",
    "print(brute_force(all_prices))\n",
    "end = time.time()\n",
    "print(f'  {end-start}')\n",
    "\n",
    "start = time.time()\n",
    "print(max_profit(all_prices))\n",
    "end = time.time()\n",
    "print(f'  {end-start}')\n",
    "\n",
    "start = time.time()\n",
    "print(greedy_profit(all_prices))\n",
    "end = time.time()\n",
    "print(f'  {end-start}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "41882b08-f2c1-4228-9d84-2dd1c1c620be",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.13.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}