c++ - 找到最多 k 个的最长二进制子序列的长度

Question

如标题所示，我需要找到最多 k 个的最长二进制子序列的长度。例如:

k = 3, binary_seq = 11100001101011010000011，答案是:10(因为最长的子序列是11100001101011010000011)

k = 1，binary_seq = 00101001001，答案是:5(因为最长的子序列是00101001001)

我做到了，但在二次时间(我猜)

#include <iostream>
#include <vector>

using namespace std;

template <typename V>
void pop_front(V & v)
{
    v.erase(v.begin());
}

int main() {
    int k,maxLength=0,lengthOfSequence;
    bool one;
    string bin_seq;
    lengthOfSequence = 1;
    vector<unsigned> myList;
    cin >> k;
    cin >> bin_seq;
    for(char num : bin_seq) {
        myList.push_back(0);
        if (num == '1') {
            for(int i = 0; i < lengthOfSequence;++i)
                ++myList[i];
        }
        for(int i = 0; i < lengthOfSequence;++i) {
            if(myList[i] <= k) {
                if (lengthOfSequence-i > maxLength) {
                    maxLength = lengthOfSequence-i;
                }
            }
        }
        lengthOfSequence++;
        while(myList[0]>k) {
            pop_front(myList);
            lengthOfSequence--;
        }

    }
    cout << maxLength << '\n';
    return 0;
}

如何以更小的时间复杂度做到这一点？

Answer 1

你可以用这个算法在 O(n) 内完成:

• 制作两个索引，一个用于所需子序列的开始，一个用于结束
• 通过增加 end 索引继续扩展序列，直到到达 k+1-st 1
的位置
• 在继续将序列扩展到 k+1-st 1 之前，通过“拉入”开头来缩小序列以跳过最早的 1 按顺序
• 每次通过增加end来扩展序列，记录序列的最大长度
• 一旦到达序列的末尾，max 将拥有最长的子序列，其中最多有 k 个。