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