UniLecs #122. max submatrix sum

kadane.py

# def check_rectangle_matrix(matrix: list):
#     """
#     Check if matrix is rectangle list matrix
#     """
#     if matrix and isinstance(matrix, list):
#         x_len = len(matrix[0])
#         for array in matrix:
#             if len(array) != x_len or not isinstance(array, list):
#                 return False
#         return True

def kadane(array: list):
    """
    Kadane's algorithm .
    Return max subarray(sublist) by element sum (max_sum, left, right)
    """
    current_sum = max_sum = array[0]
    left = tmp_left = right = 0
    for i in range(1, len(array)):
        if current_sum > 0:
            current_sum += array[i]
        else:
            current_sum = array[i]
            tmp_left = i
        if current_sum > max_sum:
            max_sum = current_sum
            left = tmp_left
            right = i
    return max_sum, left, right

def kadane2d(matrix: list):
    """
    Kadane's algorithm implementation for matrix.
    Return max submatrix by element sum (max_sum, left, up, right, down)
    """
    if not matrix:
        raise ValueError('Empty matrix')
    if not matrix[0]:
        raise ValueError('Empty matrix')
    max_sum, left, right = kadane(matrix[0])
    up = down = 0
    for y in range(0, len(matrix)):
        tmp = matrix[y]
        for y1 in range(y+1, len(matrix)):
            array1 = matrix[y1]
            tmp = [tmp[i] + array1[i] for i in range(len(tmp))]
            current_sum, tmp_left, tmp_right = kadane(tmp)
            if current_sum > max_sum:
                max_sum = current_sum
                left = tmp_left
                right = tmp_right
                up = y
                down = y1
    return max_sum, left, up, right, down