最长上升子序列问题
有一个长为n的数列a0,a1,...,a(n-1)。请求出这个序列中最长的上升子序列的长度。
上升子序列指的是对于任意的i j都满足ai aj的子序列。
1≤n≤1000
0≤ai≤1000000输入
n=5
a={4,2,3,1,5}输出
3（注：2，3，5）分析
首先用暴力解法 O(n^2) 遍历每一种可能性 可以很轻松的得到结果
接着 使用dp法 但是比较晦涩
package BlueCup.Eight_DP_greed;
import java.util.Scanner;
import static java.lang.Math.max;
public class 最长上升子序列 {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int n = cin.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = cin.nextInt();
}
System.out.println(f(a, n));
System.out.println(dp(a, n));
System.out.println(dp01(a, n));
}
/**
* dp[i] 长度为i的L O(nlgn)
* IS
* @param a
* @param n
* @return
*/
private static int dp01(int a[], int n) {
int[] dp = new int[n + 1];
int p;//记录dp更新的最后位置
dp[p = 1] = a[0];//长度为1的最长递增子序列，初始化为第一个元素
for (int i = 1; i < a.length; i++) {
if (a[i] > dp[p])//新元素和dp的关系 如果遇到比i大的数 那就 存进去 并指针后移
dp[p++ + 1] = a[i];//递增子序列长度增加
else {//递增子序列长度 不 增加
//扫描dp 替换第一个比arr[i]大的dp
for (int j = 0; j <= p; j++) {
if (dp[j] > dp[i])//
dp[j] = a[i];
}
}
}
return p;
}
/**
* dp 递推 逐步解决
* O(n^2)pd[i] 是以i结尾的 序列
* j是待比较 i是比较的目标
*
* @param a
* @param n
* @return
*/
private static int dp(int[] a, int n) {
int[] dp = new int[n];
dp[0] = 1;
for (int i = 1; i < n; i++) {
int cnt = 1;
for (int j = i - 1; j >= 0; j--) {
if (a[i] > a[j])
cnt = max(cnt, dp[j] + 1);//所有dp表中最大的~
}
dp[i] = cnt;
}
int ans = -1;
for (int i : dp) ans = max(ans, i);//最后遍历一遍dp[i]
return ans;
}
/**
* 暴力解法 o(n^2)
*
* @param a
* @param n
* @return
*/
private static int f(int[] a, int n) {
int maxCnt = 0;
for (int i = 0; i < n; i++) {
int cnt = 1;//从1 开始 最短就是1
int p = i;//记录被大于的数值索引
for (int j = i + 1; j < n; j++) {
if (a[j] > a[p]) {
cnt++;
p = j;
}
}
maxCnt = max(maxCnt, cnt);
}
return maxCnt;
}
}
本文作者：Author： 寒光博客
文章标题：[LanQiao]最长上升子序列问题 动态规划
本文地址：https://dxoca.cn/Algorithm/275.html 百度已收录
版权说明：若无注明，本文皆为“Dxoca's blog （寒光博客）”原创，转载请保留文章出处。
本文地址：https://dxoca.cn/Algorithm/275.html 百度已收录
版权说明：若无注明，本文皆为“Dxoca's blog （寒光博客）”原创，转载请保留文章出处。
那个小埋点脸好像不会响应，点胸（大雾）倒是反映挺快的
hentai?!
三大子序列问题
雾 这么晚还没睡啊
这种$O(n^2)$的用不到
嘿嘿 但是拿来学习嘛φ(￣∇￣o)