Golang O(n) solution with brief explain


  • 0
    L
    func deleteAndEarn(nums []int) int {
        if nums == nil || len(nums) == 0 {
            return 0
        }
        
        // use counter sort instead
        counter := make([]int, 10001)
        for _, v := range nums {
            counter[v]++
        }
        
        // using counter for Dynamic Programing formula
        // f[i] = max(f[i-2] + counter[i] * i, f[i-1])
        if counter[2] <<= 1; counter[2] < counter[1] {
            counter[2] = counter[1]
        }
        for i := 3; i <= 10000; i++ {
            if counter[i] = counter[i-2] + counter[i] * i; counter[i] < counter[i-1] {
                counter[i] = counter[i-1]
            }
        }
        
        return counter[10000]
    }
    

Log in to reply
 

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