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 的大作中提到】
: 有个一个N*N的array，里面的元素是pos或者neg的整数，求最大的一个所有元素和最大
: subarray。
|
x***y
发帖数: 633 | 3 old question, you can check 2D-Kadane algorithm...
【在 K******g 的大作中提到】
: 有个一个N*N的array，里面的元素是pos或者neg的整数，求最大的一个所有元素和最大
: subarray。
|
I**A
发帖数: 2345 | 4 题目嘛意思？
【在 x***y 的大作中提到】
: 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 的大作中提到】
: 题目嘛意思？
|
I**A
发帖数: 2345 | 6 thanks
the
【在 x***y 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 任选两行作为上下边，有O(n^2)种方法，对于每一种情况，进行一维最大子数组处理，
: 复杂度为O(n)。
: 总复杂度为O(n^3)。
|
K******g
发帖数: 1870 | 10 这个方法不错
【在 h**6 的大作中提到】
: 任选两行作为上下边，有O(n^2)种方法，对于每一种情况，进行一维最大子数组处理，
: 复杂度为O(n)。
: 总复杂度为O(n^3)。
|
