{"id":10022,"date":"2023-04-30T07:58:44","date_gmt":"2023-04-30T14:58:44","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=10022"},"modified":"2023-04-30T07:59:23","modified_gmt":"2023-04-30T14:59:23","slug":"leetcode-2656-maximum-sum-with-exactly-k-elements","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/greedy\/leetcode-2656-maximum-sum-with-exactly-k-elements\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2656. Maximum Sum With Exactly K Elements"},"content":{"rendered":"\n

You are given a 0-indexed<\/strong> integer array nums<\/code> and an integer k<\/code>. Your task is to perform the following operation exactly<\/strong> k<\/code> times in order to maximize your score:<\/p>\n\n\n\n

  1. Select an element m<\/code> from nums<\/code>.<\/li>
  2. Remove the selected element m<\/code> from the array.<\/li>
  3. Add a new element with a value of m + 1<\/code> to the array.<\/li>
  4. Increase your score by m<\/code>.<\/li><\/ol>\n\n\n\n

    Return the maximum score you can achieve after performing the operation exactly<\/em> k<\/code> times.<\/em><\/p>\n\n\n\n

    Example 1:<\/strong><\/p>\n\n\n\n

    Input:<\/strong> nums = [1,2,3,4,5], k = 3\nOutput:<\/strong> 18\nExplanation:<\/strong> We need to choose exactly 3 elements from nums to maximize the sum.\nFor the first iteration, we choose 5. Then sum is 5 and nums = [1,2,3,4,6]\nFor the second iteration, we choose 6. Then sum is 5 + 6 and nums = [1,2,3,4,7]\nFor the third iteration, we choose 7. Then sum is 5 + 6 + 7 = 18 and nums = [1,2,3,4,8]\nSo, we will return 18.\nIt can be proven, that 18 is the maximum answer that we can achieve.\n<\/pre>\n\n\n\n
    Example 2:<\/strong><\/p>\n\n\n\n
    Input:<\/strong> nums = [5,5,5], k = 2\nOutput:<\/strong> 11\nExplanation:<\/strong> We need to choose exactly 2 elements from nums to maximize the sum.\nFor the first iteration, we choose 5. Then sum is 5 and nums = [5,5,6]\nFor the second iteration, we choose 6. Then sum is 5 + 6 = 11 and nums = [5,5,7]\nSo, we will return 11.\nIt can be proven, that 11 is the maximum answer that we can achieve.\n<\/pre>\n\n\n\n
    Constraints:<\/strong><\/p>\n\n\n\n
    • 1 <= nums.length <= 100<\/code><\/li>
    • 1 <= nums[i] <= 100<\/code><\/li>
    • 1 <= k <= 100<\/code><\/li><\/ul>\n\n\n\n
      Solution: Greedy<\/strong><\/h2>\n\n\n\n
      Always to chose the largest element from the array.<\/p>\n\n\n\n
      We can find the largest element of the array m, then the total score will be
      m + (m + 1) + (m + 2) + … + (m + k – 1),
      We can use summation formula of arithmetic sequence to compute that in O(1)
      ans = (m + (m + k – 1)) * k \/ 2<\/p>\n\n\n\n
      Time complexity: O(n)
      Space complexity: O(1)<\/p>\n\n\n\n
      \n
      C++<\/h2>\n
      \n\n
      \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int maximizeSum(vector& nums, int k) {\n    int m = *max_element(begin(nums), end(nums));\n    return (m + m + k - 1) * k \/ 2;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
      You are given a 0-indexed integer array nums and an integer k. Your task is to perform the following operation exactly k times in order to maximize your score: Select an element m from nums. Remove…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[51],"tags":[222,88,31],"class_list":["post-10022","post","type-post","status-publish","format-standard","hentry","category-greedy","tag-easy","tag-greedy","tag-math","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/10022","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=10022"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/10022\/revisions"}],"predecessor-version":[{"id":10024,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/10022\/revisions\/10024"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=10022"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=10022"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=10022"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}