mediumDynamic Programming 1DIndian domain~25 min
Maximize Cashback While Voiding Adjacent Tiers
A wallet app offers cashback coupons of various rupee values. Claiming all coupons of a value earns their total, but voids every coupon worth one rupee more or one rupee less. Maximize the cashback.
Problem
Given an integer array nums of coupon values, in one operation you pick a value v, earn the sum of all coupons equal to v, and then delete every coupon equal to v-1 and v+1. Repeat any number of times. Return the maximum total cashback you can earn.
Input
An integer array nums of coupon values.
Output
An integer: the maximum total earnable.
Constraints
- 1 <= nums.length <= 20000
- 1 <= nums[i] <= 10^4
Examples
Example 1
Input
nums = [3,4,2]
Output
6
Claim 4 (earns 4, voids 3); then claim 2 (earns 2). Total 6.
Example 2
Input
nums = [2,2,3,3,3,4]
Output
9
Claim all 3s (earns 9), voiding 2s and 4s.