813. Largest Sum of Averages 最大平均值和的分组

转载 作者：大佬之路 更新时间：2024-01-31 14:16:47 26 4

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

class Solution:
    def largestSumOfAverages(self, A, K):
        """
        :type A: List[int]
        :type K: int
        :rtype: float
        """
        n = len(A)
        m_ = [[0 for i in range(n + 1)] for j in range(K + 1)]
        sum_ = [0] * (n + 1)
        for i in range(1, n + 1):
            sum_[i] = sum_[i - 1] + A[i - 1]
        return self.LSA(A, sum_, m_, n, K)

    Largest sum of averages for first n elements in A partioned into K groups
    def LSA(self, A, sum_, m_, n, k):
        if m_[k][n] > 0: return m_[k][n]
        if k == 1: return sum_[n] / n
        for i in range(k - 1, n):
            m_[k][n] = max(m_[k][n], self.LSA(A, sum_, m_, i, k - 1) + (sum_[n] - sum_[i]) / (n - i))
        return m_[k][n]

26 4 0

• mysql - 按 parent 分组，但不按 child 分组

  您好，我正在处理 BIRT 报告。我有一个查询，我必须对父级的重复数据进行分组，但子级也不能分组! 在我的查询中: item 是父项，item_ledger_entry 是子项。我有来自 item.N

• google-analytics - 为什么 MCF channel 分组≠默认 channel 分组？

  我正在使用 GA API。 这是针对 MCF 目标报告(底部)的标准目标完成指标表(顶部) 看一下这个: 总数加起来 (12,238)，但看看按 channel 分组的分割有多么不同!我以为这些会很接

• OrientDB 分组

  我正在开发一个流量计数器，我想获得 IP 和重复计数，但是如何？ 就像是 :select ip, count(ip) from Redirect 返回 : null total ip count 重定

• Java正则表达式(分组)

  我尝试编写一个正则表达式来匹配条件表达式，例如: a!=2 1+2=2+a 我尝试提取运算符。我当前的正则表达式是“.+([!=<>]+).+” 但问题是匹配器总是尝试匹配组中可能的最短字符串

• 分组、平均的SQL子查询问题

  在 MS Transact SQL 中，假设我有一个这样的表(订单): Order Date Order Total Customer # 09/30/2008 8

• MySQL:分组

  我想按 m.ID 分组，并对每个 m.id 求和 (pm.amount_construction* prod.anzahl) 实际上我有以下结果: Meterial_id | amount_const

• PostgreSQL 分组

  我想根据多列中的值对值进行分组。这是一个例子: 我想得到输出: {{-30,-50,20},{-20,30,60},{-30,NULL or other value, 20}} 我设法到达: SELE

• MySql 分组

  我正在尝试找出运行此查询的最佳方式。我基本上需要返回在我们的系统中只下了一个订单的客户的“登录”字段列表(登录字段基本上是客户 ID/ key )。 我们系统的一些背景...... 客户在同一日期下的

• MYSQL - 分组

  给定以下mysql结果集: id code name importance '1234', 'ID-CS-B', 'Chocolate Sauce'

• python - 分组

  大家好，我的数据框中有以下列: LC_REF 1 DT 16 2C 2 DT 16 2C 3 DT 16 2C 1 DT 16 3C 6 DT 16 3C 3

• MongoDB 分组

  我有这样的 mongoDB 集合 { "_id" : "EkKTRrpH4FY9AuRLj", "stage" : 10, }, { "_id" : "EkKTRrpH4FY9

• Python 分组

  假设我有一组数据对，其中 index 0 是值，index 1 是类型: input = [ ('11013331', 'KAT'), ('9085267',

• java中用stream进行去重，排序，分组

  java中用stream进行去重，排序，分组 一、distinct 1. 八大基本数据类型 List collect = ListUtil.of(1, 2, 3, 1, 2).stream().fil

• SQL - 如何添加具有平均值的列，分组

  基本上，我从 TABLE_A 中的这个开始 France - 100 France - 200 France - 300 Mexico - 50 Mexico - 50 Mexico - 56 Pol

• 正则表达式，分组，查找最后一个匹配项

  我希望这个正则表达式 ([A-Z]+)$ 将选择此示例中的最后一次出现: AB.012.00.022ABC-1 AB.013.00.022AB-1 AB.014.00.022ABAB-1 但我没有匹配

• 数据透视表中的 SQL 分组

  我创建了一个数据透视表，但数据没有组合在一起。 任何人都可以帮助我获得所需的格式吗？ 我为获取数据透视表而编写的查询: DECLARE @cols AS NVARCHAR(MAX), -- f

• SQL选择并按一段时间(时间戳)分组

  我想按时间段(月，周，日，小时，...)选择计数和分组。例如，我想选择行数并将它们按 24 小时分组。 我的表创建如下。日期是时间戳。 CREATE TABLE MSG ( MSG_ID dec

• 围绕间隙的 SQL 分组

  在 SQL Server 2005 中，我有一个包含如下数据的表: WTN------------Date 555-111-1212 2009-01-01 555-111-1212 2009-

• python - 按多列对数据框中的连续条目进行聚类/分组

  题 假设我有 k 个标量列，如果它们沿着每列彼此在一定距离内，我想对它们进行分组。 假设简单 k 是 2 并且它们是我唯一的列。 pd.DataFrame(list(zip(sorted(choice

• pandas - 分组、拆分和选取数据框中的顶行

  问题 在以下数据框中 df : import random import pandas as pd random.seed(999) sz = 50 qty = {'one': 1, 'two': 2