Funcia
Lv.3dpgridkadaneprefix-sum

합이 가장 큰 직사각형 영역

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

R행 C열의 땅이 칸으로 나뉘어 있고, grid[i][j]는 i행 j열 칸에서 얻는 이익입니다(음수면 손해).

변이 격자선과 나란한 직사각형 영역 하나를 골라 그 안의 모든 칸의 이익을 얻으려고 합니다. 영역은 적어도 한 칸을 포함해야 합니다. 얻을 수 있는 이익 합의 최댓값을 반환하세요.

입출력 예

gridresult
[[1, -2, 3], [-4, 5, 6], [7, -8, 9]]18
[[-5, -2], [-3, -9]]-2
[[2, 3, -100, 4]]5

입출력 예 설명

예 1 — 맨 오른쪽 열 전체(3 + 6 + 9 = 18)가 가장 큽니다. 격자 전체의 합은 17이고, 오른쪽 아래 2×2 영역은 5 + 6 - 8 + 9 = 12입니다.

예 2 — 모든 칸이 음수이므로 가장 덜 손해인 칸 하나(-2)를 고릅니다.

예 3 — 가운데의 -100을 피해 왼쪽 두 칸(2 + 3 = 5)을 고릅니다.

효율성

이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.

함수 시그니처

solution(grid: int[][]) → long

제한 사항

  • 1≤R=1 \le R = grid.length ≤300\le 300, 1≤C=1 \le C = grid[i].length ≤300\le 300 (모든 행의 길이는 같습니다)
  • −106≤-10^6 \le grid[i][j] ≤106\le 10^6
  • 답은 32비트 정수를 넘을 수 있습니다.

기대 복잡도

시간
O(R^2 * C)
공간
O(C)

입출력 예

grid기대 출력
[[1,-2,3],[-4,5,6],[7,-8,9]]18
[[-5,-2],[-3,-9]]-2
[[2,3,-100,4]]5

힌트

힌트

직사각형은 "위쪽 행 top, 아래쪽 행 bottom, 왼쪽 열, 오른쪽 열"로 정해집니다. 네 가지를 모두 고르면 O(R2C2)O(R^2 C^2)가지입니다.

위·아래 행을 고정하면 남은 문제는 1차원입니다. 열마다 top~bottom 행의 합을 col[j]에 모아 두면, 그 행 범위의 최대 직사각형은 배열 col의 최대 연속 부분합과 같습니다. 이것은 카데인 알고리즘으로 O(C)O(C)에 구합니다.

for top in 0..R-1:
    col = [0] * C
    for bottom in top..R-1:
        col[j] += grid[bottom][j]   (모든 j)
        best = max(best, kadane(col))

bottom을 늘릴 때 col에 한 행만 더하면 되므로 전체 O(R2C)O(R^2 C)입니다. 행보다 열이 적으면 행과 열을 바꿔 생각해도 됩니다. 합은 64비트 정수로 다루세요.

복잡도 목표

2차원 누적 합으로 모든 직사각형을 확인하는 O(R2C2)O(R^2 C^2) 풀이는 효율성 테스트에서 시간 초과가 납니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)200 ms추정
C++ (GCC, gnu++23)200 ms도출됨
Python 3.133490 ms도출됨
Java 251034 ms도출됨
Kotlin 2.4 (JVM)1400 ms추정
C# 14 (.NET 10)1400 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample03입력·출력 공개
correctness4011판정만
performance604판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.