Commitc252df5

authored

feat: add houseRobber implementation (TheAlgorithms#1282)

1 parent002b10a commitc252df5Copy full SHA for c252df5

File tree

+43

-0

lines changed

Dynamic-Programming/Sliding-Window
- HouseRobber.js
- test
  - HouseRobber.test.js

+43

-0

lines changed

Lines changed: 23 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,23 @@`
	`1`	`+/**`
	`2`	`+ *@function houseRobber`
	`3`	`+ *@description Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.`
	`4`	`+ *@param {number[]} nums`
	`5`	`+ *@return {number}`
	`6`	`+ *@see [Leetcode link](https://leetcode.com/problems/house-robber/)`
	`7`	`+ */`
	`8`	`+exportconsthouseRobber=(nums)=>{`
	`9`	`+constlength=nums.length`
	`10`	`+`
	`11`	`+if(length===0)return0`
	`12`	`+if(length===1)returnnums[0]`
	`13`	`+if(length===2)returnMath.max(nums[0],nums[1])`
	`14`	`+`
	`15`	`+constdp=Array(length)// last element of this array always contains biggest loot possible`
	`16`	`+dp[0]=nums[0]`
	`17`	`+dp[1]=Math.max(nums[0],nums[1])`
	`18`	`+`
	`19`	`+for(leti=2;i<length;i++){`
	`20`	`+dp[i]=Math.max(nums[i]+dp[i-2],dp[i-1])`
	`21`	`+}`
	`22`	`+returndp[length-1]`
	`23`	`+}`

Lines changed: 20 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,20 @@`
	`1`	`+import{houseRobber}from'../HouseRobber'`
	`2`	`+`
	`3`	`+describe('houseRobber',()=>{`
	`4`	`+it('expects to return 0 when argument is empty array',()=>{`
	`5`	`+expect(houseRobber([])).toBe(0)`
	`6`	`+})`
	`7`	`+`
	`8`	`+it('expects to return element at index 0 when argument is array of length one',()=>{`
	`9`	`+expect(houseRobber([9])).toBe(9)`
	`10`	`+})`
	`11`	`+`
	`12`	`+it('expects to return greater number when argument is an array of length two',()=>{`
	`13`	`+expect(houseRobber([3,6])).toBe(6)`
	`14`	`+})`
	`15`	`+`
	`16`	`+it('expects to return the maximum loot possible',()=>{`
	`17`	`+expect(houseRobber([1,2,3,1])).toBe(4)`
	`18`	`+expect(houseRobber([2,7,9,3,1])).toBe(12)`
	`19`	`+})`
	`20`	`+})`

Comments

(0)