c********t
发帖数: 5706 | 1 在int matrix上求最大submatrix sum。
我在想对一维arr, 求最大连续sum, 有linear解法。
为什么2D似乎只有O(N^3)的解法？ | p*****2
发帖数: 21240 | 2
本身已经N^2了。
【在 c********t 的大作中提到】
: 在int matrix上求最大submatrix sum。
: 我在想对一维arr, 求最大连续sum, 有linear解法。
: 为什么2D似乎只有O(N^3)的解法？
| c********t
发帖数: 5706 | 3 对Maximal Rectangle, 还有rain water drop 2D的解法就感觉充分利用了一维方法得
到O(n^2)，一维是O(n)
但这道题，CC解法似乎只把一维的方法用在2D的column上，但我也想不出怎么能更充分
利用一维的方法。
【在 p*****2 的大作中提到】
:
: 本身已经N^2了。
|
|
