K******g 发帖数: 1870 | 1 有个一个N*N的array,里面的元素是pos或者neg的整数,求最大的一个所有元素和最大
subarray。 |
I**A 发帖数: 2345 | 2 N*N是个matrix
看过求array的最大subarray
木见过怎么求matrix的subarray,你是说submatrix maybe?
【在 K******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 有个一个N*N的array,里面的元素是pos或者neg的整数,求最大的一个所有元素和最大 : subarray。
|
x***y 发帖数: 633 | 3 old question, you can check 2D-Kadane algorithm...
【在 K******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 有个一个N*N的array,里面的元素是pos或者neg的整数,求最大的一个所有元素和最大 : subarray。
|
I**A 发帖数: 2345 | 4 题目嘛意思?
【在 x***y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : old question, you can check 2D-Kadane algorithm...
|
x***y 发帖数: 633 | 5 find a submatrix with the largest sum, similarly to find a subarray with the
largest sum in an array...
【在 I**A 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 题目嘛意思?
|
I**A 发帖数: 2345 | 6 thanks
the
【在 x***y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : find a submatrix with the largest sum, similarly to find a subarray with the : largest sum in an array...
|
i***1 发帖数: 95 | 7 programming pearls 8.7.13
【在 I**A 的大作中提到】![](/moin_static193/solenoid/img/up.png) : thanks : : the
|
h**6 发帖数: 4160 | 8 任选两行作为上下边,有O(n^2)种方法,对于每一种情况,进行一维最大子数组处理,
复杂度为O(n)。
总复杂度为O(n^3)。 |
t****a 发帖数: 1212 | 9 But if the columns/rows in the sub-matrix is not adjacent?
【在 h**6 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 任选两行作为上下边,有O(n^2)种方法,对于每一种情况,进行一维最大子数组处理, : 复杂度为O(n)。 : 总复杂度为O(n^3)。
|
K******g 发帖数: 1870 | 10 这个方法不错
【在 h**6 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 任选两行作为上下边,有O(n^2)种方法,对于每一种情况,进行一维最大子数组处理, : 复杂度为O(n)。 : 总复杂度为O(n^3)。
|