Home HouseRobber - improving performance java code
Reply: 0

HouseRobber - improving performance java code

Kalyan Chavali
1#
Kalyan Chavali Published in 2017-12-07 22:26:45Z

I'm trying to solve the houseRobber problem from LeetCode.

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

My approach

  1. produce a list of all possible indices of the array that represent the houses on the street. This is where recursion occurs. List of such indices of an array with size n = list of such indices for n-1 array and (that for n-2 array + n added to each of the possibility)
  2. Iterate through those indices and get the max money / code

This works but takes a lot of time for medium-sized arrays (length 30-50).Therefore, I am using dynamic programming technique to reduce the number of calls but even then it is taking a lot of time for array of size 37 and more.

package graphprog4;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

public class HouseRobber {

    public ArrayList<ArrayList<Integer>> addNtoC(ArrayList<ArrayList<Integer>> arr, int n){
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        for(ArrayList<Integer> tm: arr){
            ArrayList<Integer> tmp = (ArrayList<Integer>) tm.clone();
            tmp.add(n);
            res.add(tmp);
        }
        return res;
    }

    public ArrayList<ArrayList<Integer>> getCombs(int n, Map<Integer,ArrayList<ArrayList<Integer>>> mem){

        //memory check
        if(mem.containsKey(n)){
            return mem.get(n);
        }



        //base cases
        if(n==0){
            ArrayList<Integer> rs = new ArrayList<Integer>();
            ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
            rs.add(0);
            res.add(rs);
            mem.put(0, res);
            return res;
        }       
        if(n==1){
            ArrayList<Integer> rs = new ArrayList<Integer>();
            ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
            ArrayList<Integer> rs1 = new ArrayList<Integer>();
            rs.add(0);
            rs1.add(1);
            res.add(rs);
            res.add(rs1);
            mem.put(1, res);
            return res;
        }

        ArrayList<ArrayList<Integer>> prev2 = getCombs(n-2,mem);
        ArrayList<ArrayList<Integer>> prevN = addNtoC(prev2, n);
        ArrayList<ArrayList<Integer>> res = getCombs(n-1,mem);

        ArrayList<ArrayList<Integer>> tmp = (ArrayList<ArrayList<Integer>>) res.clone();
        tmp.addAll(prevN);

        mem.put(n, tmp);

        return tmp;
    }

    int getMaxGold(int[] nums){
        int maxGold = 0;
        if(nums == null){
            return 0;
        }

        int n = nums.length;
        if (n == 0){
            return 0;
        }
        Map<Integer,ArrayList<ArrayList<Integer>>> mem = new HashMap<Integer,ArrayList<ArrayList<Integer>>>();
        ArrayList<ArrayList<Integer>> res = getCombs(n-1,mem);

        for(ArrayList<Integer> arr: res){
            int gd = 0; 
            for(int x: arr){
                gd += nums[x];
            }

            if(maxGold<gd){
                maxGold = gd;
            }
        }
        return maxGold;
    }

    public static void main(String[] args) {
        HouseRobber rb = new HouseRobber();
        int[] nums = {183, 219, 57, 193, 94, 233, 202, 154, 65, 240, 97, 234, 100, 249, 186, 66, 90, 238, 168, 128, 177, 235, 50, 81, 185, 165, 217, 207, 88, 80, 112, 78, 135, 62, 228, 247, 211};
        int answer = rb.getMaxGold(nums);
        System.out.println(answer);
    }
}

Please tell me what I can do to improve the performance.

You need to login account before you can post.

About| Privacy statement| Terms of Service| Advertising| Contact us| Help| Sitemap|
Processed in 0.311605 second(s) , Gzip On .

© 2016 Powered by mzan.com design MATCHINFO