740.delete-and-earn.md

740. Delete and Earn

Dynamic Programming

If we take the nums[i], then we can't take the nums[i-1] and nums[i+1]. It's a kind of House Robber problem, the difference is that we can't take the consecutive numbers (conflict by value, not by index). So we just take a look at the unique numbers and calculate the gains (value * count) for each number.

nums = [2, 2, 3, 3, 3, 4]

count = {
    2: 2,
    3: 3,
    4: 1
}

// Unique numbers after sorting
values = [2, 3, 4]
counts = [2, 3, 1]
gains  = [4, 9, 4]

• Define dp[i] = maximum gains if we take the values[i].
• State transition:
  • If values[i] == values[i-1] + 1, it's consecutive, we can only take current or (skip + take previous):

  dp[i] = max(dp[i - 1], dp[i - 2] + gains[i])

  • If it's not consecutive, we can take the current + previous:

  dp[i] = dp[i - 1] + gains[i]

• Finally, return the last element of dp.

fun deleteAndEarn(nums: IntArray): Int {
    val count = HashMap<Int, Int>()
    for (num in nums) {
        count[num] = (count[num] ?: 0) + 1
    }
    val values = count.keys.toIntArray()
    values.sort()

    val n = values.size
    val gains = IntArray(n) {
        val v = values[it] 
        v * (count[v] ?: 0)
    }
    val dp = IntArray(n)
    dp[0] = gains.first()
    for (i in 1 until n) {
        if (values[i - 1] + 1 == values[i]) { // Consecutive
            val take = gains[i] + (if (i - 2 >= 0) dp[i - 2] else 0)
            val skip = dp[i - 1]
            dp[i] = maxOf(take, skip)
        } else {
            dp[i] = gains[i] + dp[i - 1]
        }
    }
    return dp.last()
}

• Time Complexity: O(n log n)
• Space Complexity: O(n)

Or equivalent, we can use two variables for dp[i-1] and dp[i-2] to save space.

TODO: Implement the space-optimized version.