JS O(n^2) time and O(n) time solutions


  • 0
    Y
    // https://leetcode.com/problems/house-robber/
    function rob(numbers) {
      if (numbers.length === 0) {
        return 0
      }
      const dp = numbers.slice()
      for (let i = 0; i < numbers.length; i++) {
        let next = dp[i]
        for (let j = 0; j < i - 1; j++) {
          next = Math.max(next, dp[j] + dp[i])
        }
        dp[i] = next
      }
      return Math.max(...dp)
    }
    
    function rob(houses) {
      if (houses.length === 0) {
        return 0
      }
      let [robPrev, notRobPrev] = [0, 0]
      for (let i = 0; i < houses.length; i++) {
        [robPrev, notRobPrev] = [houses[i] + notRobPrev, Math.max(robPrev, notRobPrev)]
      }
      return Math.max(robPrev, notRobPrev)
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.