最长非递增子序列在一个二进制字符串中

1. 题目简介

给定一个二进制字符串，求其最长的非递增子序列的长度。

2. 算法简介

2.1 动态规划

动态规划算法经常被用来解决最长子序列的问题。该算法的时间复杂度为$n^2$，其中$n$是序列的长度。

该算法的思路是定义一个状态数组$dp[i]$表示以第$i$个数字结尾的最长非递增子序列的长度。然后，从前往后遍历数组，对于每一个元素，枚举其前面的所有元素，如果前面的元素小于等于当前元素，则可将其加入到当前元素的最长非递增子序列中，更新状态。最终，取状态数组中的最大值即可得到最长非递增子序列的长度。

2.2 贪心算法

贪心算法可以通过维护一个递减的数组来得到最长非递增子序列的长度，时间复杂度为$O(nlogn)$。

该算法的思路是定义一个数组$tail$，表示当前维护的最长非递增子序列，初始为空。然后，遍历整个数组，对于每一个元素，如果其大于$tail$数组的最后一个元素，直接将其加入到$tail$数组的末尾；否则，在$tail$数组中二分查找第一个小于等于当前元素的位置，将其替换为当前元素。最终，$tail$数组的长度即为最长非递增子序列的长度。

3. 代码实现

下面给出动态规划算法和贪心算法的代码实现。

3.1 动态规划

#include <bits/stdc++.h>

using namespace std;
const int N = 100010;
int dp[N];
int main() 
{
    string s;
    cin >> s;
    int n = s.size();
    int ans = 0;
    for (int i = 0; i < n; i++) 
    {
        dp[i] = 1;
        for (int j = 0; j < i; j++)
            if (s[j] >= s[i])
                dp[i] = max(dp[i], dp[j] + 1);
        ans = max(ans, dp[i]);
    }
    cout << ans << endl;
    return 0;
}

3.2 贪心算法

#include <bits/stdc++.h>

using namespace std;
const int N = 100010;
int tail[N];
int main() 
{
    string s;
    cin >> s;
    int n = s.size();
    int len = 0;
    for (int i = 0; i < n; i++) 
    {
        int l = 0, r = len;
        while (l < r) 
        {
            int mid = l + r + 1 >> 1;
            if (tail[mid] <= s[i]) l = mid;
            else r = mid - 1;
        }
        tail[l + 1] = s[i];
        len = max(len, l + 1);
    }
    cout << len << endl;
    return 0;
}

4. 性能比较

由于贪心算法时间复杂度更低，因此在实际应用中更加常用。下面以随机生成的100000位的二进制字符串为例，比较两种算法的性能表现。

4.1 动态规划

$ time ./dp

0101010100......
real

0m41.233s
user

0m41.219s
sys

0m0.001s

4.2 贪心算法

$ time ./greedy

0101010100......
real

0m0.050s
user

0m0.044s
sys

0m0.001s

可以看到，贪心算法的运行时间远远小于动态规划算法。

5. 总结

本文介绍了如何使用动态规划算法和贪心算法求解一个二进制字符串中最长的非递增子序列的长度，并对两种算法的时间复杂度进行了比较。在实际应用中，由于贪心算法的时间复杂度更低，因此更加常用。