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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

K Items With the Maximum Sum

Number: 2715

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

Given a bag containing items labeled 1, 0, and -1, with numOnes items labeled 1, numZeros items labeled 0, and numNegOnes items labeled -1, the goal is to pick exactly k items such that the sum of the selected items is maximized.

Key Insights

  • To maximize the sum, always choose items with value 1 first.
  • Next, choose items with value 0 if additional items are needed because they do not change the sum.
  • Only choose items with value -1 if the required number of items (k) exceeds the total available ones and zeros.
  • The maximum sum is given by: (number of ones chosen) minus (number of negative ones chosen) which simplifies to: min(k, numOnes) - max(0, k - numOnes - numZeros).

Space and Time Complexity

Time Complexity: O(1) - The solution computes the result in constant time regardless of the input sizes. Space Complexity: O(1) - Only a few variables are used, independent of input sizes.

Solution

This problem is solved using a greedy approach. The strategy is to:

  1. Pick as many items with value 1 as possible, but not more than k.
  2. Use items with value 0 next if k has not been reached, as they don't affect the sum.
  3. If more items are needed (i.e., k > numOnes + numZeros), select the remaining items from those with value -1, which will decrease the sum.
  4. The final sum is calculated as the positive contributions from ones minus the negative contributions from -1 items that must be chosen.

Code Solutions

# Function to calculate maximum sum of k items
def k_max_sum(numOnes, numZeros, numNegOnes, k):
    # Calculate how many ones to pick (maximum possible without exceeding k)
    pick_ones = min(k, numOnes)
    # If k > numOnes + numZeros, we must pick negative items.
    pick_negatives = max(0, k - numOnes - numZeros)
    # Final computed sum: ones add positive value, negatives reduce the sum.
    return pick_ones - pick_negatives

# Example usage and testing
if __name__ == "__main__":
    # Example 1
    print(k_max_sum(3, 2, 0, 2))  # Expected output: 2
    # Example 2
    print(k_max_sum(3, 2, 0, 4))  # Expected output: 3
← Back to All Questions