S**Y
发帖数: 136 | 1 1. 一个matrix有正有负,求和最大的sub matrix
2. Given two arrays A [1..n] and B[1..m], find the smallest window in A that
co
ntains all elements of B. That is, find a pair such that A[l..k] conta
ins B[1..m]
For example, given A = 3,1,5,7,3,5,2 and B = 5,3 then the smallest window is
[3,5].
多谢. | w***g
发帖数: 5958 | 2 我觉得这两题都得穷搜，没动态规划算法。
1. 可以利用矩阵部分和加速子矩阵和，穷搜需要O(n^2), n=矩阵大小。还有种办法是把
问题转化为一维数组求和最大子串：确定两列，那么求这两列夹着的那些子矩阵中最大
者就变成了一维问题，然后还是穷举所有两列的组合。如果矩阵大小是mxn，那么需要时
间为O(m^2xn).不过这种办法程序编起来没前面那种方法快。
that
conta
is
【在 S**Y 的大作中提到】
: 1. 一个matrix有正有负,求和最大的sub matrix
: 2. Given two arrays A [1..n] and B[1..m], find the smallest window in A that
: co
: ntains all elements of B. That is, find a pair such that A[l..k] conta
: ins B[1..m]
: For example, given A = 3,1,5,7,3,5,2 and B = 5,3 then the smallest window is
: [3,5].
: 多谢.
| w***g
发帖数: 5958 | 3 第二题估计也得穷举。不过我觉得可以用下面的办法加速：
假设B中元素各不相同（这个假设很容易去掉）。
用下标p1,p2确定A的一个子串，用map C记录p1 p2之间B中各个元素出现的次数。
初始状态
p1 = p2 = 1
C[..] = 0
然后执行下面的循环：
10: C[A[p2]]++
while ((p1 < p2) && C[A[p1]] > 1) {
p1++;
C[A[p1]]--;
}
这时如果C中所有元素都是1，那么p1和p2就确定了一个包含B中所有元素的子串
，记录
p2++
goto 10
that
conta
is
【在 S**Y 的大作中提到】
: 1. 一个matrix有正有负,求和最大的sub matrix
: 2. Given two arrays A [1..n] and B[1..m], find the smallest window in A that
: co
: ntains all elements of B. That is, find a pair such that A[l..k] conta
: ins B[1..m]
: For example, given A = 3,1,5,7,3,5,2 and B = 5,3 then the smallest window is
: [3,5].
: 多谢.
| w***g
发帖数: 5958 | 4 说一下一维问题的O(n)解法。一列正负相间的数A[1..n]求和最大的子串（任意子串都可
以通过把相邻的整数或负数求和转化成正负相间）。
用p1和p2确定一个子串，用s记录这个子串的和。
初始状态
p1 = p2 = 1
s = A[1]
然后执行下面的循环：
10: p2++;
if (A[p2] >= 0) {
s += A[p2]
goto 10
}
p1和p2确定一个局部最大子串，将其和全局最大子串比较
if (s + A[p2] > 0) {
s += A[p2];
p2++;
}
else {
p2++;
p1 = p2;
s = A[p2];
}
goto 10
是把
要时
【在 w***g 的大作中提到】
: 我觉得这两题都得穷搜，没动态规划算法。
: 1. 可以利用矩阵部分和加速子矩阵和，穷搜需要O(n^2), n=矩阵大小。还有种办法是把
: 问题转化为一维数组求和最大子串：确定两列，那么求这两列夹着的那些子矩阵中最大
: 者就变成了一维问题，然后还是穷举所有两列的组合。如果矩阵大小是mxn，那么需要时
: 间为O(m^2xn).不过这种办法程序编起来没前面那种方法快。
:
: that
: conta
: is
| d**a
发帖数: 84 | 5 2.
就是一个常见题吧，搞两个指针l,r
l=r=0;
while(l
increase r until all ele of B are in A[l..r]
update current min window
increase l until some ele of B is not in A[l..r]
}
that
conta
is
【在 S**Y 的大作中提到】
: 1. 一个matrix有正有负,求和最大的sub matrix
: 2. Given two arrays A [1..n] and B[1..m], find the smallest window in A that
: co
: ntains all elements of B. That is, find a pair such that A[l..k] conta
: ins B[1..m]
: For example, given A = 3,1,5,7,3,5,2 and B = 5,3 then the smallest window is
: [3,5].
: 多谢.
|
|
