// 1.cpp : 定义控制台应用程序的入口点。
//
#include
"stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <
string.h>
#include <limits.h>
int dropLength(
int *A,
int n)
{
int max=
0;
int* B = (
int*)malloc(
sizeof(
int)*
n);
int i =
0,k =
0;
B[0] =
1;
for(k=
1;k<=n-
1;k++)
//计算B[0],B[1],...,B[n-1]
{
for(i=
0;i<=k-
1;i++)
//将A[0...k-1]和A[k]比较
{
if(A[i] >= A[k] && B[i] >
max)
max =
B[i];
}
B[k] = max+
1;
max =
0;
//必须清零
}
return B[n-
1];
}
int main()
{
int A[] = {
2,
1,
0,-
1,-
2};
int length = dropLength(A,
5);
printf("%d ",length);
return 0;
}
令B[k]是以a[k]为结尾的最长下降子序列的长度，则有
1、当k=0时，B[k]=1;
2、当k>=1时有，B【k】 = max{B[i]| a[i]>=a[k],i=0,1,2,...,k-1} + 1;
法二：对序列A进行降序排序变为B，问题转化为求A和B的最长公共子序列。
转载于:https://www.cnblogs.com/welsh-android-learning/p/3495340.html
