HDURevenge of Segment Tree（第二長的遞增子序列）

HDURevenge of Segment Tree（第二長的遞增子序列）

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;
}