ACM模版

描述

题解

一开始想着有O(N)的解法，可是苦思冥想没能想出来，很尴尬……
最后用排序递归解了，然后又学习了大牛们的高校O(N)解法。

这道题的大致意思还真不好讲，我们可以通过样例来理解这道题：
模拟这道题，可以发现，最开始我们会选取12和10，

9 10 2 -1 3 -5 0 -3 1 12 5 8 -2 6 4

接着，我们会选取的一定是3（一定在10和12之间），那么我们不难发现，这里有些贪心的意味，所以我们需要先对序列进行排序。

12 10 9 8 6 5 4 3 2 1 0 -1 -2 -3 -5

那么回到上一步开始考虑，去过12和10后，接着是9和8，可是因为其不再10和12之间，所以舍去，直到3。

9 10 2 -1 3 -5 0 -3 1 12 5 8 -2 6 4

那么下一个数字一定在10和3之间或者3和12之间，那么我们这时就应该理解了，下一个数字一定在前三个选择的数的两种组合之间，所以，可以递归解之，但是这里需要进行一下剪枝，否则会超时1s，One代码第31到34行即为剪枝。

接着，我们来说一下O(N)的解法，当一回时候诸葛亮吧。
这里需要用到单调栈解，不断入栈，入栈前将小于即将入栈的元素出栈，维护单调递增栈。然后需要考虑到两种情况，第一，栈中剩余的结点作为B数组，第二，每一个新结点与栈内小于该结点的最大number加一作为B数组长度。不断更新max，最后输出即可。

代码

One：

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

const int MAXN = 5e4 + 5;

struct b
{
    int B;
    int order;
} B[MAXN];

int A[MAXN];
int N;
int ans = 0;

bool cmp(b a, b aa)
{
    return a.B > aa.B;
}

void solve(int left, int right, int pos, int K)
{
    if (right - left <= 1)
    {
        ans = ans > K ? ans : K;
        return ;
    }
    if (K + right - left - 1 <= ans)
    {
        return ;
    }
    while (B[pos].order > right || B[pos].order < left)
    {
        pos++;
    }
    solve(left, B[pos].order, pos + 1, K + 1);
    solve(B[pos].order, right, pos + 1, K + 1);
    return ;
}

int main()
{
    cin >> N;

    for (int i = 0; i < N; i++)
    {
        scanf("%d", A + i);
        B[i].B = A[i];
        B[i].order = i;
    }
    sort(B, B + N, cmp);

    solve(0, N - 1, 0, 0);

    cout << ans << '\n';
}

Two：

#include <stdio.h>

#define MAX 50001

typedef struct
{
    int value;
    int number; // 这个点加入数组后，选择这个点作为B数组的元素时，B数组的最大长度
} node;

node a[MAX];    // 单调栈

int max_(int a, int b)
{
    return a > b ? a : b;
}

int main()
{
    int n, max = 0, index = 0, x;
    scanf("%d", &n);

    // 第一个结点入栈
    scanf("%d", &x);
    a[0].value = x;
    a[0].number = 1;
    for (int i = 1; i < n; i++)
    {
        scanf("%d", &x);
        int number = 0;
        while (index >= 0 && x > a[index].value)    // 栈不为空，将所有小于x的结点出队列
        {
            number = max_(number, a[index].number);
            index--;
        }
        index++;
        number++;
        number = max_(index + 1, number);           // 选取栈内剩余点的作为B数组
        max = max_(max, number);                    // 更新结果
        // 将此结点入栈
        a[index].value = x;
        a[index].number = number;
    }
    printf("%d", max);
}