rearrange-array-to-maximize-prefix-score

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

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

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

Return the maximum score you can achieve.

&nbsp;
Example 1:

<pre>
Input: nums = [2,-1,0,1,-3,3,-3]
Output: 6
Explanation: We can rearrange the array into nums = [2,3,1,-1,-3,0,-3].
prefix = [2,5,6,5,2,2,-1], so the score is 6.
It can be shown that 6 is the maximum score we can obtain.
</pre>

Example 2:

<pre>
Input: nums = [-2,-3,0]
Output: 0
Explanation: Any rearrangement of the array will result in a score of 0.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums.length &lt;= 105</code></li>
	<li><code>-106 &lt;= nums[i] &lt;= 106</code></li>
</ul>

maxScore

Rearrange Array to Maximize Prefix Score

Two City Scheduling

two-city-scheduling

两地调度

Greedy

Array

Prefix Sum

Sorting

给你一个下标从 0 开始的整数数组 <code>nums</code> 。你可以将 <code>nums</code> 中的元素按 任意顺序 重排（包括给定顺序）。

令 <code>prefix</code> 为一个数组，它包含了 <code>nums</code> 重新排列后的前缀和。换句话说，<code>prefix[i]</code> 是 <code>nums</code> 重新排列后下标从 <code>0</code> 到 <code>i</code> 的元素之和。<code>nums</code> 的 分数 是 <code>prefix</code> 数组中正整数的个数。

返回可以得到的最大分数。

&nbsp;

示例 1：

<pre>输入：nums = [2,-1,0,1,-3,3,-3]
输出：6
解释：数组重排为 nums = [2,3,1,-1,-3,0,-3] 。
prefix = [2,5,6,5,2,2,-1] ，分数为 6 。
可以证明 6 是能够得到的最大分数。
</pre>

示例 2：

<pre>输入：nums = [-2,-3,0]
输出：0
解释：不管怎么重排数组得到的分数都是 0 。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= nums.length &lt;= 105</code></li>
	<li><code>-106 &lt;= nums[i] &lt;= 106</code></li>
</ul>