{"id":9981,"date":"2023-03-11T20:50:58","date_gmt":"2023-03-12T04:50:58","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9981"},"modified":"2023-03-11T20:53:27","modified_gmt":"2023-03-12T04:53:27","slug":"leetcode-2587-rearrange-array-to-maximize-prefix-score","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/greedy\/leetcode-2587-rearrange-array-to-maximize-prefix-score\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2587. Rearrange Array to Maximize Prefix Score"},"content":{"rendered":"\n

You are given a 0-indexed<\/strong> integer array nums<\/code>. You can rearrange the elements of nums<\/code> to any order<\/strong> (including the given order).<\/p>\n\n\n\n

Let prefix<\/code> be the array containing the prefix sums of nums<\/code> after rearranging it. In other words, prefix[i]<\/code> is the sum of the elements from 0<\/code> to i<\/code> in nums<\/code> after rearranging it. The score<\/strong> of nums<\/code> is the number of positive integers in the array prefix<\/code>.<\/p>\n\n\n\n

Return the maximum score you can achieve<\/em>.<\/p>\n\n\n\n

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

Input:<\/strong> nums = [2,-1,0,1,-3,3,-3]\nOutput:<\/strong> 6\nExplanation:<\/strong> We can rearrange the array into nums = [2,3,1,-1,-3,0,-3].\nprefix = [2,5,6,5,2,2,-1], so the score is 6.\nIt can be shown that 6 is the maximum score we can obtain.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> nums = [-2,-3,0]\nOutput:<\/strong> 0\nExplanation:<\/strong> Any rearrangement of the array will result in a score of 0.\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= nums.length <= 105<\/sup><\/code><\/li>
  • -106<\/sup> <= nums[i] <= 106<\/sup><\/code><\/li><\/ul>\n\n\n\n
    Solution: Greedy<\/strong><\/h2>\n\n\n\n
    Sort the numbers in descending order.<\/p>\n\n\n\n
    Time complexity: O(nlogn)
    Space complexity: O(1)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int maxScore(vector& nums) {\n    sort(rbegin(nums), rend(nums));\n    int ans = 0;\n    for (long i = 0, s = 0; i < nums.size(); ++i) {\n      s += nums[i];\n      if (s <= 0) break;\n      ++ans;\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    You are given a 0-indexed integer array nums. You can rearrange the elements of nums to any order (including the given order). Let prefix be the array containing the prefix sums of nums after rearranging it.…<\/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":[20,88,200],"class_list":["post-9981","post","type-post","status-publish","format-standard","hentry","category-greedy","tag-array","tag-greedy","tag-prefix-sum","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9981","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=9981"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9981\/revisions"}],"predecessor-version":[{"id":9983,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9981\/revisions\/9983"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9981"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9981"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9981"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}