You are given an N*M 2D matrix, Each cell contains a number and no two cells have the same number. We have to select one element from each of the N rows, let selected elements be c1,c2,...cN.
The cost of Matrix is defined as - the sum of (ci-sj)(1<=i,j<=N) where sj represents the greatest element in jth row that is <=ci, If no such sj exists then sj=0.

We have to find the maximum possible cost of the matrix.

For Example:-
If N=M=3 and matrix = [[4,3,2], [6,1,5], [8,9,7]]
Now the values for c1 can be 4,3 or 2, values for c2 can be 6,1 or 5 and values for c3 can be 8,9 or 7
If we select c1=4, c2=6 and c3=9

• Cost of c1 = (4-4) (4-1) (4-0)=7, here s1 = 4(greatest element <=c1=4 in 1st row), s2 = 1, s3 = 0(as no element is <=c3=9 in 3rd row)
• similarly, Cost of c2 = (6-4) (6-6) (6-0)=8
• cost of c3 = (9-4) (9-6) (9-9) = 8
• Total Cost = 7 8 8 = 23
  This is the maximum score that we can get from any values of c1,c2,c3.

Another Example:-
If Matrix = [[2,22,28,30],[21,5,14,4],[20,6,15,23]] then maximum cost would be 60.

I tried choosing the maximum element from each row as ci, but this does not work. Can anyone tell how we can approach and solve this problem?

Edit: I have tried long for coding and understanding this but am unable to do so successfully, here is what I am able to code until now, this passes some cases but fails some.

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

CodePudding user response：

You can solve this in O(N log N) time, where N is the total number of elements.

First, we can define the value of a nonnegative integer x independently of what row it is in. Letting max_at_most(row, x) denote a function returning the largest element in row that is at most x, or 0 if none exists.

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

Now, max_at_most is a monotonic function of x for a fixed row, and it only changes at most length(row) times for each row, which we can use to calculate it quickly.

Find all unique elements in your matrix, and track the row indices where each element occurs. Sort the unique elements. Now, if we iterate over the elements in order, we can track the largest elements seen in each row (and also the sum of max_at_most(row, x) over all rows) in O(1) time.

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)