213. House Robber II.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.\n",
    "\n",
    "Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def rob(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if len(nums)==0:\n",
    "            return 0\n",
    "        if len(nums)==1:\n",
    "            return nums[0]\n",
    "        a=self.helper(nums,0,len(nums)-2)\n",
    "        b=self.helper(nums,1,len(nums)-1)\n",
    "        return max(a,b)\n",
    "    def helper(self,nums,lo,hi):\n",
    "        maxm=[0,0]\n",
    "        for i in range(lo,hi+1):\n",
    "            i0=i%2\n",
    "            i1=(i+1)%2\n",
    "            maxm[i0]=max(maxm[i0]+nums[i],maxm[i1])\n",
    "        return max(maxm)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[i for i in range(0,0)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This problem is similar to the previous problem House Robber , with one extra condition that houses are arranged in circle . This condition makes the difference that if we are robbing last house then we can not rob the first house and if we are robbing the first house then we can not rob the last house . this is because first and last houses are neighbor of each other .\n",
    "To solve this ques we can think 2 cases --\n",
    "\n",
    "case 1 ==> take the first house and skip the last house (take input array from first element to one before last element)======>> houseRob(a,0,a.size()-2)\n",
    "\n",
    "case 2 ===> take the last house and skip the first house ( take input array from second element to last element) =======>> houseRob(a,1,a.size()-1)\n",
    "\n",
    "Now we have to take the maximum of case 1 and case 2 this will be the answer .\n",
    "\n",
    " max(houseRob(a,0,a.size()-2),houseRob(a,1,a.size()-1))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python [default]",
   "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}