HDU 5087 Revenge of LIS II（BestCoder Round #16）（次长上升子序列）

#include<stdio.h>
#include<string.h>
#include<queue>
#include<math.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;

const int N=1e3+10;
const int INF=0x3f3f3f3f;
const int MOD=1e9+7;

typedef long long LL;

LL a[N];
int dp[N][2], b[2*N]; ///dp[i][0]保存以a[i]结尾的最长递增子序列的长度，dp[i][1]保存以a[i]结尾的次长递增子序列的长度
        
int main ()
{
    int T, n, i, j, k, x, y;

    scanf("%d", &T);

    while (T--)
    {
        scanf("%d", &n);
        for (i = 0; i < n; i++)
            scanf("%lld", &a[i]);

        memset(dp, 0, sizeof(dp));
        for (i = 0; i < n; i++) 
            dp[i][0] = 1; ///将最长递增子序列的长度初始化为1（大于次长递增子序列）
        memset(b, 0, sizeof(b));
        k = 0;

        for (i = 0; i < n; i++)
        {
            for (j = 0; j < i; j++)
            {
                if (a[j] < a[i])
                {
                    x = dp[j][0]+1; ///如果前面比后面小，说明递增序列+1
                    y = dp[j][1]+1;

                    if (x > dp[i][0]) swap(x, dp[i][0]); ///因为次长递增子序列<=最长递增子序列，所以dp[i][1]更新的值<=dp[i][0]
                    dp[i][1] = max(dp[i][1], x);
                    dp[i][1] = max(dp[i][1], y);
                }
            }

            b[k++] = dp[i][0];
            b[k++] = dp[i][1];
        }

        sort(b, b+k);

        printf("%d\n", b[k-2]);
    }

    return 0;
}