最长上升子序列：
思路：用数组b[1000]存放在i之前共有多少个上升子字符。并找出其中最长的，记录为len，遍历完0-i之后的len即为i之前最长上升子序列，因此用a[i]记录在i之前的最长上升子序列，共下一个元素参考。
在听了郭炜老师的课后，按照他的思路，把这俩题解出来，供以后回忆。
#include#include int a[1000];int b[1000];int main(){ int n,ans = 0; scanf("%d",&n); for(int i = 0;i < n;i++) scanf("%d",&a[i]),b[i] = 1; for(int i = 1;i < n;i++){ int len = 0; for(int j = 0;j < i;j++) if(a[j] < a[i] && b[j] > len) len = b[j]; b[i]+=len; } for(int i = 0;i < n;i++) if(b[i] > ans) ans = b[i]; printf("%d",ans); return 0;}
最长公共子序列：
代码很简单，画图很麻烦，我也不善表达，这个博主的文章想表达的和我的代码思路相同，请看
#include#include #define max(a,b) a>b?a:bint main(){ char a[1000],b[1000]; scanf("%s%s",a,b); int lenA = strlen(a),lenB = strlen(b); int Maxlen[100][100]; for(int i = 0;i < lenA;i++) Maxlen[i][0] = 0; for(int j = 0;j < lenB;j++) Maxlen[0][j] = 0; for(int i = 1;i <= lenA;i++) for(int j = 1;j <= lenB;j++){ if(a[i-1] == b[j-1]) Maxlen[i][j] = Maxlen[i-1][j-1]+1; else Maxlen[i][j] = max(Maxlen[i-1][j],Maxlen[i][j-1]); } int len = 0; for(int i = 1;i <= lenA;i++) for(int j = 1;j <= lenB;j++) if(Maxlen[i][j] > len) len = Maxlen[i][j]; printf("%d",len); return 0;}