LIS的三种基本解法

compaq · 2024-05-21 10:34:36 · 算法·理论

LIS的定义

一个长度为n序列a[]中最长的单调递增的子序列。

解法1：动态规划

• 设f[i]表示以a[i]为结尾的LIS长度。

• f[i] = max(f[j] + 1)(1<=j<i 且a[j] < a[i])

• 初始化：f[i] = 1

• 答案:max(f[1], f[2]... f[n])

  
  int main(){
  scanf("%d", &n);
  for(int i = 1; i <= n; i++) {
      scanf("%d", &a[i]);
      f[i] = 1;
  }
  for(int i = 1; i <= n; i++)
      for(int j = 1; j < i; j++)
          if(a[j] < a[i]) f[i] = max(f[i], f[j] + 1);
  for(int i = 1; i <= n; i++) 
      ans = max(ans, f[i]);
  printf("%d\n", ans);
  return 0;
  }

**局限性：** 这里枚举$i$，还需要枚举$j$，所以时间复杂度为$O(n^2$），当$n$范围较大时不适用。

#### 解法2：贪心+二分
对于多组拥有同样长度的上升子序列，比如(2,3,7）和(2,3,4)两个子序列长度都是3。显然，4比7小，那么将来出现的数，更加有机会接在4的后面，即第二组在以后可能接上的数会更多。

- 设$f[len]$表示$LIS$长度为$len$时结尾元素的最小值。

- 显然，$f[]$数组是一个单调递增的数组。

维护$f[]$过程如下：设当前枚举到第$i$个数$a[i]$,$len$表示$f[]$当前长度。

- 若$a[i] > f[len]$, 则$ f[++len] = a[i]$;
- 否则，在$f[]$中找出第一个满足大于等于$a[i]$的数，替换掉$f[]$中的数，保持该长度时，数值尽可能小
```cpp
int main(){
    scanf("%d", &n);
    for(int i = 1; i<=n; i++)
        scanf("%d",a + i);

    for(int i = 1; i <= n; i++){
        if( a[i] > f[len] )
            f[++len] = a[i];
        else{
            int tmp = lower_bound(f + 1,f + len + 1, a[i]) - f; 
                f[tmp] = a[i];
        }
    }
    printf("%d\n", len);
    return 0;
}

算法时间复杂度为O(nlogn)

思考：若求的是最长不下降子序列，该如何修改？ 比如这组数据：

10

3 2 2 2 2 2 3 2 2 2

for(int i = 1; i <= n; i++){
        if( a[i] >= f[len] ) //此处要把改为>=
            f[++len] = a[i];
        else{
            int tmp = upper_bound(f + 1,f + len + 1, a[i]) - f; //不是用lower_bound
                f[tmp] = a[i];
        }
    }

解法3：树状数组维护

回顾解法1的状态转移方程，修改方程如下：