学步园

/*
47.创新工场：
求一个数组的最长递减子序列
比如{9，4，3，2，5，4，3，2}的最长递减子序列为{9，5，4，3，2} 

一看就是DP题目
设源数组为A，我们定义一个长度与A相同的辅助数组为B，
B[i]表示以A[i]结尾的最长递减序列的长度。
B[i]=max{B[k]+1，A[i]<A[k] && 0=<k<i}，B[0]=1

题目要求输出递减的序列
倒着来 B[i]表示以A[i]结尾的最长递减序列的长度，最大的肯定就是末尾元素
如何 搜寻前面的数？B[i]+1==B[k] && A[i]>A[k]时，A[i]就是前一个元素；
 
还有种方法输出，就是再用一个数组，存储前一个递减序列的位置
if(a[i]<a[j]&&dp[j]+1>max)//是递减的 
	max=dp[j]+1;
	id=j； 
*/
#include<iostream>
#include<stdio.h>
using namespace std;

int dp[100],id[100];

void printPath(int a[],int dp[],int k)
{
	int i;
	for(i=k;i>=0;i--)//k表示的是递减序列的位置 
	{
		if(a[i]>a[k]&&dp[i]+1==dp[k])
		{
			printPath(a,dp,i);
			break;
		}
	}
	printf("%d ",a[k]);
}

void max_dec_subseq(int a[],int len)
{
	int i,j,max,start=0,max_all;
	
	dp[0]=1;//一个本身就是递减序列 
	max_all=0;//放最大的递减长度的位置 
	
	for(i=1;i<len;i++)
	{
		max=0; 
		for(j=0;j<i;j++) 
		{
			if(a[i]<a[j]&&dp[j]+1>max)//是递减的 
				max=dp[j]+1;
		}
		dp[i]=max;
		if(dp[max_all]<dp[i])//取最长的递减序列的位置 
			max_all=i;	
	}
		
	printPath(a,dp,max_all);	
}

int main()
{
	int a[]={9,4,3,2,5,4,3,2};
	int b[]={9,8,6,5,4,3,2,1,9};
	max_dec_subseq(a,sizeof(a)/sizeof(int));
	printf("\n");
	max_dec_subseq(b,sizeof(b)/sizeof(int));
	return 0;
}