일단 문제 링크는 https://www.acmicpc.net/problem/22992

처음엔 갱신.. 부분합.. 이라길래 2차원 세그먼트 트리 써야하나? 싶었는데

스티커를 자르는 과정에서 테두리 부분합의 최대를 구하기 위해선 O(H + W) 과정을 거쳐야 될 거 같아서 일단 아래 알고리즘처럼 짜봤어요

베이스는 배열에서 부분합의 최대를 구하는 카데인 알고리즘이에요


대충 이렇게 진행해서 매 순간의 sum 중 최대치를 갱신해서 둥글게 도는 테두리 배열 중 최대 부분합을 찾아내요


근데 문제 이해를 잘못한 건지, 반례가 있는건지 잘 모르겠어요

- 스티커 위에 새 스티커를 붙이면 이전의 스티커가 이미 획득한 영역의 점수는 받지 못하는가?

아닌 거 같아요 테스트 케이스 1번 보면 꼬박꼬박 잘 받는 거 같던데..

- 인덱싱을 잘못 짠게 아닐가?

이건 테스트 다 돌려본 결과 잘 나왔어요

움.. 먼가 반례가 있는 거 같은데


* 반례 *

1   2   3
1   0 -1
-6 1   2

사유: 마지막 인덱스를 합하지 못함