matrix maximum element all recursive giving wrong value

I am trying to implement a recursive solution to find the maximum value in a matrix, however, instead of getting 1000 I am getting 550, can you help say why?

def row_max(l, s, e): #l is the row list, s is the start index, e is the end
    if e - s <= 1:
        mx = l[e]
        if l
展开收缩
 > l[e]:
            mx = l
展开收缩
        return mx
    else:
        q = (s + e) // 2
        lft_mx = row_max(l, s, q)
        rgt_mx = row_max(l, q+1, e)
        res_mx = lft_mx
        if (rgt_mx > lft_mx):
            res_mx = rgt_mx
        return res_mx
        
def maxi2(M, s, c, r): #M is matrix, s is the start of rows which will be 0 at first, c is index of the last column, r is index of the last row, 
    mr = ((s+r) // 2)
    if (r - s) <= 1:
        return row_max(M[r], 0, c)
    pm1 = maxi2(M, s, c, mr-1)
    pm2 = maxi2(M, mr, c, r)
    maxi = pm1
    if (pm2 > pm1):
        maxi = pm2
    return maxi

Input:

m = [[1,2,3,60], 
     [5,6,40,8],
     [9,1000,11,12], 
     [13,19,18,550]]
res = maxi2(m, 0, 3, 3)
print(res)

Output
550

Expected Output:
1000

Also, ignoring space complexity, is this the best possible time complexity algorithm for max in matrix?

The check if (r - s) <= 1: - or rather the logic following it - is wrong: r and s are inclusive indices in your scenario. Thus you have one or two rows to consider, but you only consider r, not s (unlike if e - s <= 1: in row_max, where you consider both entries).

Simply replace the if (r - s) <= 1: and everything nested within it with

if r == s:
    return row_max(M[r], 0, c)

You have to adapt your two recursive calls to maxi2 then, since mr-1 could now be less than r if mr == r:

pm1 = maxi2(M, s, c, mr)
pm2 = maxi2(M, mr+1, c, r)

(you have already figured that out yourself it seems)

You will get the expected output of 1000 since the row containing it is not ignored anymore.

As for the time complexity: This is indeed linear time. The space usage is logarithmic in the width and height of the matrix.

I would recommend just using a simple iterative solution or even better, using iterators and flatten, which will also have linear time complexity.

This is what a "pythonic" solution might look like (effectively a max of the "flattened" matrix):

def matrix_max(m):
    return max(elem for row in m for elem in row)

or even shorter, as Kelly Bundy proposes, a max of max's: return max(map(max, m))

note that you don't need to pass width and height since these are stored with the lists.

I corrected it the following way:

def maxi2(M, s, c, r):
    mr = ((s+r) // 2)
    if (r - s) <= 0:
        return row_max(M[r], 0, c)
    pm1 = maxi2(M, s, c, mr) #no mr-1
    pm2 = maxi2(M, mr+1, c, r) #but mr+1
    maxi = pm1
    if (pm2 > pm1):
        maxi = pm2
    return maxi