Divide_n_Conquer.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Divide-and-Conquer\n",
    "## The maximum-subarray problem\n",
    "The maximum subarray problem is a task to find the series of contiguous elements with the maximum sum in any given array.\n",
    "\n",
    "### The brute-force solution\n",
    "One way of doing this can be to create a *prefix sum array* and then just try out all the possible pairs. In an array of $n$ elements this would result in $\\binom{n}{2}$ pairs that means $\\Theta(n^2)$ "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "array = [int(i) for i in input().split()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "def prefix(arr):\n",
    "    pre = [arr[0]]\n",
    "    for i in range(1,len(arr)):\n",
    "        pre.append(pre[i-1]+arr[i])\n",
    "    #print(pre)\n",
    "    return pre"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "def brute(arr):\n",
    "    pre = [0] + prefix(array)\n",
    "    #print(pre)\n",
    "    max = pre[0]\n",
    "    ind1, ind2 = 0, 0\n",
    "    for i in range(len(pre)):\n",
    "        for j in range(i, len(pre)):\n",
    "            if(pre[j] - pre[i] > max):\n",
    "                ind1, ind2 = i, j-1\n",
    "                max = pre[j] - pre[i]\n",
    "    return ind1, ind2, max"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(7, 10, 43)"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "array = [int(i) for i in input().split()]\n",
    "print(array)\n",
    "brute(array)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The divide-and-conquer solution\n",
    "If we want to find a *maximum sub-array* of the subarray `A[low, high]`, we can divide it from the middle to get `A[low, mid]` and `A[mid+1, high]`.\n",
    "This results in three possibilities that any contigious subarray `A[i : j]` of the `A[low, high]` must lie in one of the following:\n",
    "- entirely in `A[low, mid]`\n",
    "- entirely in `A[mid+1, high]`\n",
    "- crossing the midpoint, so that $low \\leq i \\leq mid \\leq j \\leq high$\n",
    "\n",
    "We can find the *miximum subarray* of the first and second case recursively since they are just smaller subproblems of the orignal. Thus what's left to do is to find the max subarray *crossing midpoint*. This can be done in linear time in size of the subarray `A[low, high]`. Since any such subarray is made up of two subarrays, we just need to find the maximum subarrays of the form `A[i, mid]` and `A[mid+1, j]` and then combine them to get the required max subarray crossing the midpoint. \n",
    "\n",
    "After finding the three subarrays we can pass the largest of them."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def crossingMax(A, l, m, h):\n",
    "    lmax = 0\n",
    "    lsum = -99999999\n",
    "    sum = 0\n",
    "    for i in range(m, l-1, -1):\n",
    "        sum += A[i]\n",
    "        if sum > lsum:\n",
    "            lsum = sum\n",
    "            lmax = i\n",
    "\n",
    "    rmax = 0\n",
    "    rsum = -999999\n",
    "    sum = 0\n",
    "    for j in range(m+1, h):\n",
    "        sum += A[j]\n",
    "        if sum > rsum:\n",
    "            rsum = sum\n",
    "            rmax = j\n",
    "    return lmax, rmax, lsum + rsum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "def max_subarray(A, l, h):\n",
    "    #print(\"l and h =\",l,h)\n",
    "    #print(A[l:h+1])\n",
    "    if h == l:\n",
    "        return l, h, A[l]\n",
    "    else:\n",
    "        m = (l+h)//2\n",
    "        li, lr, ls = max_subarray(A, l, m)\n",
    "        ri, rr, rs = max_subarray(A, m+1, h)\n",
    "        ci, cr, cs = crossingMax(A, l, m, h)\n",
    "\n",
    "        if ls >= rs and ls >= cs:\n",
    "            return li, lr, ls\n",
    "        elif rs >= ls and rs >= cs:\n",
    "            return ri, rr, rs\n",
    "        else:\n",
    "            return ci, cr, cs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(7, 10, 43)"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "array = [int(i) for i in input().split()]\n",
    "print(array)\n",
    "max_subarray(array, 0, len(array)-1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "9da5a1eb768521143534bf09b996f0d525d45d2d4b488be6c4304e80c1815fea"
  },
  "kernelspec": {
   "display_name": "Python 3.8.8 64-bit ('base': conda)",
   "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.8.8"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}