Chapter_04_Divide_and_Conquer/exercises_4.1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4.1 The maximum-subarray problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.1-1\n",
    "\n",
    "> What does FIND-MAXIMUM-SUBARRAY return when all elements of $A$ are negative?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(smallest_index, smallest_index, smallest_value)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.1-2\n",
    "\n",
    "> Write pseudocode for the brute-force method of solving the maximum-subarray problem. Your procedure should run in $\\Theta(n^2)$ time."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_maximum_subarray(arr):\n",
    "    sums = [0]\n",
    "    for a in arr:\n",
    "        sums.append(sums[-1] + a)\n",
    "    max_sum = -1e100\n",
    "    left_index = -1\n",
    "    right_index = -1\n",
    "    for i in range(len(arr)):\n",
    "        for j in range(i, len(arr)):\n",
    "            if sums[j + 1] - sums[i] > max_sum:\n",
    "                max_sum = sums[j + 1] - sums[i]\n",
    "                left_index = i\n",
    "                right_index = j\n",
    "    return left_index, right_index, max_sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.1-3\n",
    "\n",
    "> Implement both the brute-force and recursive algorithms for the maximumsubarray problem on your own computer. What problem size $n_0$ gives the crossover point at which the recursive algorithm beats the brute-force algorithm? Then, change the base case of the recursive algorithm to use the brute-force algorithm whenever the problem size is less than $n_0$. Does that change the crossover point?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_max_crossing_subarray(arr, low, mid, high):\n",
    "    left_sum = -1e100\n",
    "    sum = 0\n",
    "    for i in range(mid - 1, low - 1, -1):\n",
    "        sum = sum + arr[i]\n",
    "        if sum > left_sum:\n",
    "            left_sum = sum\n",
    "            max_left = i\n",
    "    right_sum = -1e100\n",
    "    sum = 0\n",
    "    for j in range(mid, high):\n",
    "        sum = sum + arr[j]\n",
    "        if sum > right_sum:\n",
    "            right_sum = sum\n",
    "            max_right = j\n",
    "    return max_left, max_right, left_sum + right_sum\n",
    "\n",
    "def find_maximum_subarray(arr, low, high):\n",
    "    if low >= high:\n",
    "        return -1, -1, -1e100\n",
    "    if low + 1 == high:\n",
    "        return low, low, arr[low]\n",
    "    mid = (low + high) // 2\n",
    "    left_low, left_high, left_sum = find_maximum_subarray(arr, low, mid)\n",
    "    right_low, right_high, right_sum = find_maximum_subarray(arr, mid, high)\n",
    "    cross_low, cross_high, cross_sum = find_max_crossing_subarray(arr, low, mid, high)\n",
    "    if left_sum >= right_sum and left_sum >= cross_sum:\n",
    "        return left_low, left_high, left_sum\n",
    "    if right_sum >= left_sum and right_sum >= cross_sum:\n",
    "        return right_low, right_high, right_sum\n",
    "    return cross_low, cross_high, cross_sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.1-4\n",
    "\n",
    "> Suppose we change the definition of the maximum-subarray problem to allow the result to be an empty subarray, where the sum of the values of an empty subarray is 0. How would you change any of the algorithms that do not allow empty subarrays to permit an empty subarray to be the result?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Return empty if the result is negative."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.1-5\n",
    "\n",
    "> Use the following ideas to develop a nonrecursive, linear-time algorithm for the maximum-subarray problem. Start at the left end of the array, and progress toward subarray seen so far. Knowing a maximum subarray of $A[1 \\dots j]$, extend the answer to find a maximum subarray ending at index $j+1$ by using the following observation: a maximum subarray of $A[1 \\dots j+1]$ is either a maximum subarray of $A[1 \\dots j]$ or a subarray $A[i \\dots j+1]$, for some $1 \\le i \\le j + 1$. Determine a maximum subarray of the form $A[i \\dots j+1]$ in constant time based on knowing a maximum subarray ending at index $j$ ."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_maximum_subarray(arr):\n",
    "    max_sum = -1e100\n",
    "    max_left, max_right = -1, -1\n",
    "    sum = 0\n",
    "    last_left = 0\n",
    "    for i in range(len(arr)):\n",
    "        sum += arr[i]\n",
    "        if sum > max_sum:\n",
    "            max_sum = sum\n",
    "            max_left = last_left\n",
    "            max_right = i\n",
    "        if sum < 0:\n",
    "            sum = 0\n",
    "            last_left = i + 1\n",
    "    return max_left, max_right, max_sum"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}