C, 0mS, O(n) time, O(1) space, Scan backwards, DP


  • 0
    M

    Scanning backwards seemed more intuitive, let's also reuse the same array.

    The basic sub-structure can be illustrated using array of four integers. Consider nums = [1, 1, 8, 9], two possible cases for this would be:

    1. nums[0] = nums[0] + nums[2] (1 + 8)
    2. nums[0] = nums[0] + nums[3] (1 + 9)

    (8 + 1) < (1 + 9), hence the answer would be 10.

    Repeat this logic for every location while accumulating the sums.

    int rob(int* nums, int len)
    {
      int i;
    
      /* Handle the special case. */
      if (len > 2)
        nums[len - 3] += nums[len - 1];
    
      /* Run DP. */
      for (i = len - 4; i >= 0; --i)
            nums[i] += nums[i + 2] > nums[i + 3] ? nums[i + 2] :
                       nums[i + 3];
    
      /* Return larger of the two sums */
      return len > 1 ? nums[0] > nums[1] ? nums [0] : nums[1] :
                       nums[0];
    }
    

Log in to reply
 

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