K Items With the Maximum Sum

🏠 ⬅️ ➡️

There is a bag that consists of items, each item has a number 1, 0, or -1 written on it.

You are given four non-negative integers numOnes, numZeros, numNegOnes, and k.

The bag initially contains:

  • numOnes items with 1s written on them.
  • numZeroes items with 0s written on them.
  • numNegOnes items with -1s written on them.

We want to pick exactly k items among the available items. Return the maximum possible sum of numbers written on the items.

Example 1:

Input: numOnes = 3, numZeros = 2, numNegOnes = 0, k = 2 Output: 2 Explanation: We have a bag of items with numbers written on them {1, 1, 1, 0, 0}. We take 2 items with 1 written on them and get a sum in a total of 2. It can be proven that 2 is the maximum possible sum.

Example 2:

Input: numOnes = 3, numZeros = 2, numNegOnes = 0, k = 4 Output: 3 Explanation: We have a bag of items with numbers written on them {1, 1, 1, 0, 0}. We take 3 items with 1 written on them, and 1 item with 0 written on it, and get a sum in a total of 3. It can be proven that 3 is the maximum possible sum.

Constraints:

  • 0 <= numOnes, numZeros, numNegOnes <= 50
  • 0 <= k <= numOnes + numZeros + numNegOnes
Note: This problem is from LeetCode.
✅ Compiled
✅ Executed
⚠️ Correct 
program main
    implicit none

    integer :: numOnes, numZeros, numNegOnes, k, maxSum

    ! Example 1
    numOnes = 3
    numZeros = 2
    numNegOnes = 0
    k = 2
    call solve(numOnes, numZeros, numNegOnes, k)

    ! Example 2
    numOnes = 3
    numZeros = 2
    numNegOnes = 0
    k = 4
    call solve(numOnes, numZeros, numNegOnes, k)

contains

subroutine solve(numOnes, numZeros, numNegOnes, k)
    implicit none
    integer, intent(in) :: numOnes, numZeros, numNegOnes, k
    integer :: i, j, sum

    do i = 1, numOnes
        do j = 1, numZeros
            sum = i + j
            if (sum == k) then
                write (*, '(A, I0, A, I0, A, I0, A, I0, A)') &
                    "The maximum possible sum is ", i, " + ", j, " + ", numNegOnes, " = ", sum
                return
            end if
        end do
    end do

    do i = 1, numOnes
        do j = 1, numZeros
            sum = i + j + numNegOnes
            if (sum == k) then
                write (*, '(A, I0, A, I0, A, I0, A, I0, A)') &
                    "The maximum possible sum is ", i, " + ", j, " + ", numNegOnes, " = ", sum
                return
            end if
        end do
    end do

    do i = 1, numOnes
        sum = i + numNegOnes
        if (sum == k) then
            write (*, '(A, I0, A, I0, A, I0, A, I0, A)') &
                "The maximum possible sum is ", i, " + ", numNegOnes, " = ", sum
            return
        end if
    end do

    do i = 1, numZeros
        sum = i + numNegOnes
        if (sum == k) then
            write (*, '(A, I0, A, I0, A, I0, A, I0, A)') &
                "The maximum possible sum is ", i, " + ", numNegOnes, " = ", sum
            return
        end if
    end do

    write (*, '(A)') "No solution found."
end subroutine solve

end program main
✅ Compiled
✅ Executed
❌ Correct 
! This is a Fortran code for the problem

program maxSum
    implicit none
    integer, parameter :: numOnes = 3, numZeros = 2, numNegOnes = 0, k = 2
    integer :: i, j, sum

    ! Initialize the sum to 0
    sum = 0

    ! Loop through the items in the bag
    do i = 1, numOnes
        ! If the current item has a 1 written on it
        if (i == 1) then
            ! Add the current item to the sum
            sum = sum + 1
        end if
    end do

    do i = 1, numZeros
        ! If the current item has a 0 written on it
        if (i == 1) then
            ! Add the current item to the sum
            sum = sum + 0
        end if
    end do

    do i = 1, numNegOnes
        ! If the current item has a -1 written on it
        if (i == 1) then
            ! Subtract the current item from the sum
            sum = sum - 1
        end if
    end do

    ! Print the maximum possible sum
    print *, sum
end program maxSum
🌐 Data from online sources 
def max_sum(numOnes: int, numZeros: int, numNegOnes: int, k: int) -> int:
    max_sum = 0
    for i in range(k + 1):
        ones = min(i, numOnes)
        neg_ones = min(k - i, numNegOnes)
        max_sum = max(max_sum, ones - neg_ones)
    return max_sum

We want to find the maximum sum of k items that can be picked from the given bag. Iterate through 0 to k, and pick the minimum between i and numOnes as the count of ones, and pick the minimum between k-i and numNegOnes as the count of -1s. Since 1 - (-1) = 2, every 1 combined with a -1 will increase max_sum by 2. Calculate the maximum between the current max_sum and the sum of ones minus negative ones for each iteration. Return the final max_sum after the loop has finished, which will have the maximum possible sum of items.

🌐 Data from online sources 
int maxSum(int numOnes, int numZeros, int numNegOnes, int k) {
    int max_sum = 0;
    for (int i = 0; i <= k; ++i) {
        int ones = min(i, numOnes);
        int neg_ones = min(k - i, numNegOnes);
        max_sum = max(max_sum, ones - neg_ones);
    }
    return max_sum;
}

We want to find the maximum sum of k items that can be picked from the given bag. Iterate through 0 to k, and pick the minimum between i and numOnes as the count of ones, and pick the minimum between k-i and numNegOnes as the count of -1s. Since 1 - (-1) = 2, every 1 combined with a -1 will increase max_sum by 2. Calculate the maximum between the current max_sum and the sum of ones minus negative ones for each iteration. Return the final max_sum after the loop has finished, which will have the maximum possible sum of items.