We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

K Items With the Maximum Sum

Difficulty: Easy

Problem Description

Given a bag containing items with values of 1, 0, or -1, you have four non-negative integers: numOnes, numZeros, numNegOnes, and k. The task is to select exactly k items from the bag to maximize the sum of the values of the selected items.

Key Insights

  • To maximize the sum, prioritize selecting items with the highest values first.
  • The maximum contribution to the sum is from the numOnes. If k is less than or equal to numOnes, the maximum sum is simply k.
  • If k exceeds numOnes, take all numOnes and then fill the remaining selections with numZeros (which contribute 0).
  • The negative items (numNegOnes) should only be selected if absolutely necessary (i.e., if k exceeds the total number of available items).

Space and Time Complexity

Time Complexity: O(1)
Space Complexity: O(1)

Solution

To solve the problem, we will use a greedy approach:

  1. First, check how many 1s can be selected. If k is less than or equal to numOnes, the maximum sum is simply k.
  2. If k exceeds numOnes, take all numOnes (which gives a sum of numOnes), then check how many more items you can take:
    • Fill with numZeros next, which does not affect the sum.
    • If there are still remaining selections after taking numOnes and numZeros, they will have to be filled with -1 items.
  3. Calculate the final sum based on these selections.

Code Solutions

def maxKItems(numOnes, numZeros, numNegOnes, k):
    # Step 1: Calculate the maximum sum of selected k items
    if k <= numOnes:
        return k  # We can take k items all being 1
    else:
        sum_items = numOnes  # Take all ones
        k -= numOnes  # Reduce k by the number of ones taken
        if k <= numZeros:
            return sum_items  # All remaining can be zeros, sum remains the same
        else:
            return sum_items - (k - numZeros)  # Remaining must be -1's

# Example usage:
print(maxKItems(3, 2, 0, 4))  # Output: 3
← Back to All Questions