HDURevenge of Segment Tree（第二长的递增子序列）

题目大意:这题是求第二长的递增子序列。

解题思路：用n^2的算法来求LIS，可是这里还要记录一下最长的那个序列是否有多种组成方式，假设>= 2, 那么第二长的还是最长的LIS的长度，否则就是LIS - 1；

代码：

#include 
     
      #include 
      
       #include 
       
        using namespace std;const int maxn = 1005;int l[maxn], c[maxn];int arr[maxn];int main () {    int T, n;    scanf ("%d", &T);    while (T--) {        scanf ("%d", &n);        for (int i = 1; i <= n; i++)            scanf ("%d", &arr[i]);        for (int i = 1; i <= n; i++)            l[i] = c[i] = 1;        int ans = 1;         for (int i = 2; i <= n; i++) {            for (int j = 1; j < i; j++) {                if (arr[i] > arr[j]) {                    if (l[j] + 1 > l[i]) {                        l[i] = l[j] + 1;                        c[i] = c[j];                    } else if (l[j] + 1 == l[i])                        c[i] = 2;//之前直接加上c[j],结果会int溢出。导致错误。                }            }            ans = max (ans, l[i]);        }        int cnt = 0;        for (int i = 1; i <= n; i++)            if (l[i] == ans)                cnt += c[i];            if (cnt > 1)            printf ("%d\n", ans);        else            printf ("%d\n", ans - 1);    }    return 0;}