矩阵最大成本

Question

给你一个N*M2D矩阵，每个单元格包含一个数字，没有两个单元格有相同的数字。我们必须从N行中选择一个元素，让选定的元素是c1、c2、...cN。

矩阵的成本定义为- sum of (ci-sj)(1<=i，j<=N)，其中sj表示jth行中最大的元素，即<=ci，如果不存在这样的sj，则表示sj=0。

我们必须找到矩阵的最大可能成本。

例如：-

若N=M=3和矩阵= [[4,3,2], [6,1,5], [8,9,7]]

现在c1的值可以是4,3或2，c2的值可以是6,1或5，c3的值可以是8,9或7。

如果我们选择c1=4，c2=6和c3=9

(4-4)+(4-1)+(4-0)=7，= c1的

• 成本在这里s1 =4(第1行中的最大元素<=c1=4 )，s2 = 1，s3 =0(因为在第3行中没有元素是<=c3=9 )(6-4)+(6-6)+(6-0)=8
• cost of c3 = (9-4)+(9-6)+(9-9) = 8
• Total Cost = 7+8+8 = 23

这是我们可以从c1、c2、c3.的任何值中得到的最大分数。

另一个例子：-

如果矩阵= [[2,22,28,30],[21,5,14,4],[20,6,15,23]]，则最大成本为60。

我试着从每一行中选择最大元素作为ci，但这是行不通的。有人能告诉我们如何处理和解决这个问题吗？

编辑:我已经尝试了很久的编码和理解这一点，但不能成功地这样做，这里是我能够编码到现在为止，这通过一些情况，但失败的一些。

def solve(matrix):
    N = len(matrix)
    M = len(matrix[1])
    
    i = 0
    totalcost = 0
    for row in matrix:
        itotalcost = 0
        for ci in row:         
            icost = 0
            totalicost = 0
            for k in range(0, N):
                if k != i:
                    idx = 0
                    sj = 0
                    isj = 0
                    for idx in range(0, M):
                        isj = matrix[k][idx]
                        if isj <= ci and isj > sj:
                            sj = isj
                    icost = ci - sj
                    totalicost += icost
                    #print("ci=", ci, "sj", sj, "icost=", icost)
            if itotalcost < totalicost:
                itotalcost = totalicost
        i += 1
        #print("itotalcost=", itotalcost)
        totalcost += itotalcost
    return totalcost

Answer 1

您可以在O(N log N) time中解决这个问题，其中N是元素的总数。

首先，我们可以定义一个非负整数x的值，不管它在哪一行。让max_at_most(row, x)表示一个函数，该函数返回row中最多为x的最大元素，如果不存在，则返回0。

然后：value(x) = sum over all rows R of: { x - max_at_most(R, x) }

现在，max_at_most是固定行的x的单调函数，它只对每一行进行最大长度(行)的更改，我们可以使用它来快速计算。

查找矩阵中的所有唯一元素，并跟踪每个元素出现的行索引。对独特的元素进行排序。现在，如果我们按顺序迭代元素，我们就可以在O(1)时间内跟踪在每一行中看到的最大元素(以及所有行上的O(1)之和)。

def max_matrix_value(matrix: List[List[int]]) -> int:
    """Maximize the sum over all rows i, j, of (c_i - f(j, c_i)})
    where c_i must be an element of row i and f(j, c_i) is the largest
    element of row j less than or equal to c_i, or 0 if none exists."""

    num_rows = len(matrix)

    elem_to_indices = defaultdict(list)
    for index, row in enumerate(matrix):
        for elem in row:
            elem_to_indices[elem].append(index)

    current_max_element = [0] * num_rows
    current_max_sum = 0

    max_value_by_row = [0] * num_rows

    for element in sorted(elem_to_indices):

        # Update maximum element seen in each row
        for index in elem_to_indices[element]:
            difference = element - current_max_element[index]
            current_max_sum += difference
            current_max_element[index] = element

        max_value_for_element = element * num_rows - current_max_sum

        # Update maximum value achieved by row, if we have a new record
        for index in elem_to_indices[element]:
            max_value_by_row[index] = max(max_value_by_row[index],
                                          max_value_for_element)

    return sum(max_value_by_row)