第二题（NOIP2016）

#include<iostream>
using namespace std;
int lps(string seq, int i, int j) {
    int len1, len2;
    if (i == j)
        return 1;
    if (i > j)
        return 0;
    if (seq[i] == seq[j])
        return lps(seq, i+1, j-1) + 2;
    len1 = lps(seq, i, j-1);
    len2 = lps(seq, i+1, j);
    if (len1 > len2)
        return len1;
    return len2;
}
int main() {
    string seq; cin >> seq;
    int n = seq.size();
    cout << lps(seq, 0, n-1) << endl;
    return 0;
}

1. 【判断题】n 代表 seq 的长度。
   {{ select(1) }}

• 正确
• 错误

2. 【判断题】输入 acmerandacm，输出 5。
   {{ select(2) }}

• 正确
• 错误

3. 【判断题】第 7~8 行代码删去后程序仍能正常运行。
   {{ select(3) }}

• 正确
• 错误

4. 【判断题】程序最好情况下的时间复杂度为 $O(n^2)$。
   {{ select(4) }}

• 正确
• 错误

5. 【选择题】程序的最坏时间复杂度为（ ）。
   {{ select(5) }}

• $O(n\log n)$
• $O(n^2)$
• $O(n)$
• $O(2^n)$

6. 【选择题】函数 lps(seq, i, j) 的用途是（ ）。
   {{ select(6) }}

• 求字符串 seq 的最长回文子序列长度。
• 求字符串 seq 中区间 [i, j] 上的最长回文子串长度。
• 求字符串 seq 中区间 [i, j] 上的最长回文子序列长度。
• 求字符串 seq 中区间 [i, j] 上的最长相同前缀后缀长度。