vector - ベクトルの課題: 最大/最小条件に基づいてベクトルを分割する方法

Question

最近、次の問題に遭遇しました。

ランダムに分散された 0 と 1 のランダムな長さ (L) のベクトル (たとえば、[0,1,1,1,0,0,1,0]) があるとします。ベクトルを 2 つのサブに分割する必要があります。インデックス K のベクトルなので、次の条件が有効です。

• 左のサブベクトルには、K からの要素の最大数が逆順に含まれている必要があります。たとえば、0 の数は 1 の数以上である必要があります。
• 右サブベクトルには、1 の数がゼロの数以上であるなど、K+1 から始まる最大数の要素が含まれている必要があります。

たとえば、[1,1,1,1,1,1,1,1,1,0,1,0,0,0,0,0,0,0,0] 分割はインデックス 9、左ベクトルは [1,0]、右ベクトルは [0,1]

次のソリューションを書きましたが、複雑さは O(L^2) です。最悪の場合の O(L) の複雑さを伴う解決策があると思いますが、私を助けることができるものは何も見つかりません。何か案が？ありがとう

var max = 0;
var kMax = -1;

var firstZeroFound = false;

for (var i = 0; i < testVector.Length - 1; i++)
{
    if (!firstZeroFound)
    {
        if (testVector[i]) continue;
        firstZeroFound = true;
    }

    var maxZero = FindMax(testVector, i, -1, -1, false);
    if (maxZero == 0) continue;

    var maxOne = FindMax(testVector, i + 1, testVector.Length, 1, true);
    if (maxOne == 0) continue;

    if ((maxZero + maxOne) <= max)
        continue;

    max = maxOne + maxZero;
    kMax = i;

    if (max == testVector.Length)
        break;
}

Console.Write("The result is {0}", kMax); 

int FindMax(bool[] v, int start, int end, int increment, bool maximize)
{
    var max = 0;
    var sum = 0;
    var count = 0;
    var i = start;

    while (i != end)
    {
        count++;

        if (v[i])
            sum++;

        if (maximize)
        {
            if (sum * 2 >= count)
                max = count;
        }
        else if (sum * 2 <= count)
        {
            max = count;
        }

        i += increment;
    }

    return max;
}