Jave O(1) space, O(n) time optimal solution


  • 8

    Helper method returns DP solution from 0 - n-2 and 1 - n-1. Final answer is the max between two.

      public class Solution {
            public int rob(int[] nums) {
                if (nums == null || nums.length == 0)
                    return 0;
                int n = nums.length;
                if (n == 1) {
                    return nums[0];
                }
                return Math.max(robHelper(nums, 0, n - 2), robHelper(nums, 1, n - 1));
            }
            
            private int robHelper(int[] nums, int start, int end) {
                int curr, prev, prev2;
                curr = prev = prev2 = 0;
                for (int i = start; i <= end; i++) {
                    curr = Math.max(prev2 + nums[i], prev);
                    prev2 = prev;
                    prev = curr;
                }
                return curr;
            }
        }

Log in to reply
 

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