最长阳性子阵列 [英] Longest positive subarray

问题描述

数组A []仅包含'1'和'-1'

Array A[] contains only '1' and '-1'

构造数组B，其中B [i]是最长的连续子数组的长度在j处并在i处结束，其中 j< i和A [j] + .. + A [i]> 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 ++实现：

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屋！