[leetcode] 764. Largest Plus Sign

문제 : https://leetcode.com/problems/largest-plus-sign/

---

왼쪽 -> 오른쪽. 오른쪽 -> 왼쪽. 위 -> 아래. 아래 -> 위

로 탐색하면서의 subSum을 모든 위치에서 구한다.

(x,y)를 + 부호의 가운데 지점이라 할 때, (x,y)를 좌표로한 4가지 subSum들의 최소값이 + 부호의 최대 크기이다. 

모든 (x,y)을 + 부호의 가운데라 가정하고 subSum들을 이용하여 + 부호의 크기들을 구했을 때 최대값이 정답이 된다.

 

시간복잡도는 O(N^2)

공간복잡도는 4가지 subSum들을 구해둬야 하기 때문에 O(4N^2).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/764.%20Largest%20Plus%20Sign.cpp