최대 사각 부분 행렬의 합

이 문제는 주어진 이차원 배열에서 합이 최대인 사각 부분 행렬을 찾는 것입니다. 이 문제는 DP와 카데인 알고리즘을 결합하여 효율적으로 해결할 수 있습니다.

문제 정의: 주어진 n x m 크기의 이차원 배열이 있습니다. 이 배열의 모든 부분 행렬 중에서 합이 최대가 되는 사각 부분 행렬의 합을 구하세요.

풀이 단계:

• 1️⃣ 이차원 배열의 부분 행렬 합을 각 행별로 합산하여 1차원 배열 문제로 변환합니다.
• 2️⃣ 1차원 배열에서 카데인 알고리즘을 사용해 최대 연속 부분합을 찾습니다.
• 3️⃣ 모든 행 조합에 대해 위 과정을 반복하여 최댓값을 갱신합니다.

Python 코드 예제:
def max_submatrix_sum(matrix):
    n, m = len(matrix), len(matrix[0])
    max_sum = float('-inf')  # 최대값 초기화

    # 행 조합을 시작합니다.
    for start_row in range(n):
        temp_row_sum = [0] * m  # 누적합 배열 초기화

        # start_row에서 end_row까지 행을 포함하는 부분 행렬의 합 계산
        for end_row in range(start_row, n):
            # 각 열에 대해 부분 합을 구함
            for col in range(m):
                temp_row_sum[col] += matrix[end_row][col]

            # 카데인 알고리즘을 사용해 temp_row_sum에서 최대 부분합을 찾음
            current_max = max_kadane(temp_row_sum)
            max_sum = max(max_sum, current_max)  # 최댓값 갱신

    return max_sum

def max_kadane(arr):
    # 카데인 알고리즘을 사용해 1차원 배열의 최대 연속 부분합 계산
    max_current = max_global = arr[0]
    for num in arr[1:]:
        max_current = max(num, max_current + num)
        if max_current > max_global:
            max_global = max_current
    return max_global

# 예제 사용
matrix = [
    [1, 2, -1, -4, -20],
    [-8, -3, 4, 2, 1],
    [3, 8, 10, 1, 3],
    [-4, -1, 1, 7, -6]
]
print(max_submatrix_sum(matrix))  # 출력: 최대 사각 부분 행렬 합
        

설명: max_submatrix_sum 함수는 이차원 배열을 행별로 합산하여 temp_row_sum에 누적한 후, 카데인 알고리즘을 통해 최대 부분합을 구합니다. 모든 행 조합을 계산하면서 최댓값을 지속적으로 갱신합니다.