largest-sum-of-averages

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 an integer array <code>nums</code> and an integer <code>k</code>. You can partition the array into at most <code>k</code> non-empty adjacent subarrays. The score of a partition is the sum of the averages of each subarray.

Note that the partition must use every integer in <code>nums</code>, and that the score is not necessarily an integer.

Return the maximum score you can achieve of all the possible partitions. Answers within <code>10-6</code> of the actual answer will be accepted.

&nbsp;
Example 1:

<pre>
Input: nums = [9,1,2,3,9], k = 3
Output: 20.00000
Explanation: 
The best choice is to partition nums into [9], [1, 2, 3], [9]. The answer is 9 + (1 + 2 + 3) / 3 + 9 = 20.
We could have also partitioned nums into [9, 1], [2], [3, 9], for example.
That partition would lead to a score of 5 + 2 + 6 = 13, which is worse.
</pre>

Example 2:

<pre>
Input: nums = [1,2,3,4,5,6,7], k = 4
Output: 20.50000
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums.length &lt;= 100</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 104</code></li>
	<li><code>1 &lt;= k &lt;= nums.length</code></li>
</ul>

largestSumOfAverages

Largest Sum of Averages

Array

Dynamic Programming

Prefix Sum

给定数组&nbsp;<code>nums</code>&nbsp;和一个整数&nbsp;<code>k</code>&nbsp;。我们将给定的数组&nbsp;<code>nums</code>&nbsp;分成 最多&nbsp;<code>k</code>&nbsp;个非空子数组，且数组内部是连续的&nbsp;。&nbsp;分数 由每个子数组内的平均值的总和构成。

注意我们必须使用 <code>nums</code> 数组中的每一个数进行分组，并且分数不一定需要是整数。

返回我们所能得到的最大 分数 是多少。答案误差在&nbsp;<code>10-6</code>&nbsp;内被视为是正确的。

&nbsp;

示例 1:

<pre>
输入: nums = [9,1,2,3,9], k = 3
输出: 20.00000
解释: 
nums 的最优分组是[9], [1, 2, 3], [9]. 得到的分数是 9 + (1 + 2 + 3) / 3 + 9 = 20. 
我们也可以把 nums 分成[9, 1], [2], [3, 9]. 
这样的分组得到的分数为 5 + 2 + 6 = 13, 但不是最大值.
</pre>

示例 2:

<pre>
输入: nums = [1,2,3,4,5,6,7], k = 4
输出: 20.50000
</pre>

&nbsp;

提示:

<ul>
	<li><code>1 &lt;= nums.length &lt;= 100</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 104</code></li>
	<li><code>1 &lt;= k &lt;= nums.length</code></li>
</ul>