Easy O(n) time java DP solution


  • 0
    Y

    Pretty much the same idea as problem 198: https://leetcode.com/problems/house-robber/description/

    class Solution {
        public int deleteAndEarn(int[] nums) {
            int min = 10000; int max = 1;
            Map<Integer, Integer> map = new HashMap<>();
            for(int num: nums) {
                map.put(num, map.getOrDefault(num, 0) + 1);
                max = Math.max(max, num);
                min = Math.min(min, num);
            }
            int pprev = 0;
            int prev = map.getOrDefault(min, 0) * (min);
            int res = prev;
            for(int i = min + 1; i <= max; i ++) {
                res = Math.max(pprev + i * map.getOrDefault(i, 0), prev);
                pprev = prev;
                prev = res;
            }
            return res;
        }
    }
    

Log in to reply
 

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