[일반] 2차원배열의 직사각형 범위 최대합은 어떻게 구함?

[odo(earthwindfire00)]

아이디어 계속 생각중인데 누적합가지고 구할라해도 진짜 안떠오른다 

음수 포함되있음

- dc official App

[익명(210.103)]

imos법 한번 알아보셈

[EN_SA(encludingsalt)]

요런건첨알앗내

[main.cpp(codefox)]

본문은 누적합 말고 구간max쿼리 말하는거 아님?

[익명(175.119)]

삼각형도 되냐? ㅅㅂ 놀랍네

[main.cpp(codefox)]

최대부분직사각형합 말하는거같기도 하네

[ㅁ(119.202)]

O(N^3)까진 떠오르는데 어디까지 줄여야함?

[익명(180.70)]

자세히 알려줘

[귀여운뉴우비(118.235)]

arr[0][0] 부터 arr[i][j]까지의 합을 prefix_sum[i][j]에 저장하셈 입력받으면서 초기화 가능 - dc App

[귀여운뉴우비(118.235)]

그다음 3중포문으로 i행 j열에서 k사이즈 길이를 가지는 직사각형 합을 구해놓은 누적합으로 구할수 있음 - dc App

[ㄹㄹ(220.74)]

i,j 까지 누적합 구하고 포제의리로 ㄱ