algoadvance

Leetcode 2656. Maximum Sum With Exactly K Elements

Problem Statement

You are given a 0-indexed integer array nums and an integer k. Your task is to find the maximum possible sum of exactly k elements from the array.

You can choose elements more than once and place them into a list, list1, and the sum of the elements in list1 should be as large as possible.

Example 1:

Input: nums = [1,2,3,4], k = 2
Output: 8
Explanation: 
If we add the largest element 4 twice (4 + 4), we get 8 which is the largest possible sum.

Example 2:

Input: nums = [1,2,3], k = 3
Output: 9
Explanation: 
If we add the largest element 3 three times (3 + 3 + 3), we get 9 which is the largest possible sum.

Clarifying Questions

  1. Can elements be reused multiple times in the sum?
    • Yes, elements can be reused multiple times to form the list list1.
  2. Are there any constraints on the values of k and the size of the array?
    • Assume standard input size constraints for competitive programming (e.g., array size up to 10^5).
  3. Can k be larger than the size of the array?
    • Yes, k can be larger, and elements can be reused to match k.

Strategy

  1. The problem asks for the maximum sum of exactly k elements, where elements can be reused.
  2. To maximize the sum, the most optimal approach is to choose the largest element in the array and multiply it by k.
  3. Steps:
    • Find the maximum element in the array.
    • Multiply the largest element by k to get the final sum.

Code

Here is the C++ code to solve this problem:

#include <iostream>
#include <vector>
#include <algorithm>

int maxSumWithKElements(std::vector<int>& nums, int k) {
    // Find the maximum element in the array
    int maxElement = *max_element(nums.begin(), nums.end());

    // Calculate the maximum sum with exactly k elements
    return maxElement * k;
}

int main() {
    std::vector<int> nums1 = {1, 2, 3, 4};
    int k1 = 2;
    std::cout << maxSumWithKElements(nums1, k1) << std::endl; // Output: 8
    
    std::vector<int> nums2 = {1, 2, 3};
    int k2 = 3;
    std::cout << maxSumWithKElements(nums2, k2) << std::endl; // Output: 9
    
    return 0;
}

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI