算法分析
-
1、当确定了方向和起点后能跳的最长距离一定唯一,只能往某一个方向跳
-
2、起点:
a[i]
-
3、最长距离:以
a[i]
记为的最长上升子序列
时间复杂度 $O(n^2)$
参考文献
算法提高课
Java 代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int N = 110;
static int[] a = new int[N];
static int[] f = new int[N];
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(reader.readLine().trim());
while(t -- > 0)
{
int n = Integer.parseInt(reader.readLine().trim());
String[] s1 = reader.readLine().split(" ");
for(int i = 1;i <= n;i++) a[i] = Integer.parseInt(s1[i - 1]);
//正向求解LIS问题
int res = 0;
for(int i = 1;i <= n;i++)
{
f[i] = 1;
for(int j = 1;j < i;j++)
{
if(a[j] < a[i])
f[i] = Math.max(f[i], f[j] + 1);
res = Math.max(res, f[i]);
}
}
//反向求解LIS问题
for(int i = n;i >= 1;i--)
{
f[i] = 1;
for(int j = n;j > i;j --)
{
if(a[j] < a[i])
f[i] = Math.max(f[i], f[j] + 1);
res = Math.max(res, f[i]);
}
}
System.out.println(res);
}
}
}
c ++代码($O(nlogn)$版)
#include <iostream>
using namespace std;
const int N = 110;
int n, k;
int q[N],a[N];
int main()
{
cin >> k;
while(k -- > 0)
{
cin >> n;
for(int i = 1;i <= n;i ++) cin >> a[i];
int len = 0;
for(int i = 1;i <= n;i ++)
{
int l = 0, r = len;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(q[mid] < a[i]) l = mid;
else r = mid - 1;
}
q[l + 1] = a[i];
len = max(len, l + 1);
}
int res = len;
len = 0;
for(int i = 1;i <= n;i ++)
{
int l = 0, r = len;
//找到第一个比它大的位置
while(l < r)
{
int mid = l + r + 1 >> 1;
if(q[mid] > a[i]) l = mid;
else r = mid - 1;
}
q[l + 1] = a[i];
len = max(len, l + 1);
}
res = max(res, len);
cout << res << endl;
}
return 0;
}