Simple Java O(n) time. No additional variables.


  • 0
    K

    // The max cash can be computes as:
    // 1. Rob the current house + the cash accumulated so far by not robbing the previous house (OR)
    // 2. The cash accumulated so far by not robbing the current house

    // The input array is used to store the results. Therefore no extra space.

    public class Solution {
        public int rob(int[] arr) {
            if(arr.length==0) return 0;
            if(arr.length==1) return arr[0];
            if(arr.length>=2) arr[1] = Math.max(arr[0],arr[1]);
            for(int i=2;i<arr.length;i++) {
                arr[i] = Math.max(arr[i]+arr[i-2], arr[i-1]);
            }
            return arr[arr.length-1];
        }
    }
    

Log in to reply
 

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