最长正子阵列 [英] Longest positive subarray
问题描述
数组 A[] 只包含 '1' 和 '-1'
Array A[] contains only '1' and '-1'
构造数组B,其中B[i]是从j开始到i结束的最长连续子数组的长度,其中j 0
Construct array B, where B[i] is the length of the longest continuous subarray starting at j and ending at i, where j < i and A[j] + .. + A[i] > 0
明显的 O(n^2) 解决方案是:
Obvious O(n^2) solution would be:
for (int i = 0; i < A.size(); ++i) {
j = i-1;
sum = A[i];
B[i] = -1; //index which fills criteria not found
while ( j >=0 ) {
sum += A[j];
if (sum > 0)
B[i] = i - j + 1;
--j;
}
}
我正在寻找 O(n) 解决方案.
I'm looking for O(n) solution.
推荐答案
诀窍是意识到我们只需要找到最小 j 使得 (A[0] + ... + A[j-1]) == (A[0] + ... + A[i]) - 1
.A[j] + ... + A[i]
与 (A[0] + ... + A[i]) - (A[0] +... + A[j-1])
,所以一旦我们找到合适的 j,j 和 i 之间的总和将为 1.任何较早的 j 都不会产生正值,而任何较晚的 j 都不会为我们提供最长的可能序列.如果我们跟踪我们首先到达每个连续负值的位置,那么我们可以很容易地为任何给定的 i 查找合适的 j.
The trick is to realize that we only need to find the minimum j such that (A[0] + ... + A[j-1]) == (A[0] + ... + A[i]) - 1
. A[j] + ... + A[i]
is the the same as (A[0] + ... + A[i]) - (A[0] + ... + A[j-1])
, so once we find the proper j, the sum between j and i is going to be 1.
Any earlier j wouldn't produce a positive value, and any later j wouldn't give us the longest possible sequence. If we keep track of where we first reach each successive negative value, then we can easily look up the proper j for any given i.
这是一个 C++ 实现:
Here is a C++ implementation:
vector<int> solve(const vector<int> &A)
{
int n = A.size();
int sum = 0;
int min = 0;
vector<int> low_points;
low_points.push_back(-1);
// low_points[0] is the position where we first reached a sum of 0
// which is just before the first index.
vector<int> B(n,-1);
for (int i=0; i!=n; ++i) {
sum += A[i];
if (sum<min) {
min = sum;
low_points.push_back(i);
// low_points[-sum] will be the index where the sum was first
// reached.
}
else if (sum>min) {
// Go back to where the sum was one less than what it is now,
// or go all the way back to the beginning if the sum is
// positive.
int index = sum<1 ? -(sum-1) : 0;
int length = i-low_points[index];
if (length>1) {
B[i] = length;
}
}
}
return B;
}
这篇关于最长正子阵列的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!