经典动态规划问题--最长上升子序列 POJ--2533

Longest Ordered Subsequence

Description

Input

Output

Sample Input

7
1 7 3 5 9 4 8

Sample Output

4

解题思路：这一题刚开始有点卡住了，可能最近相同类型的题目做的有点多。最后看了提示想到的方法，不用递归去做。原题中要我们求解最大上升子序列，那么我们可以把问题分解为以求第 i 个数为结尾的子序列的最大上升子序列。而第i个数的解和前面i-1个数的解是存在联系的，这就是解题的核心。知道前面i-1个数的解后来求第i个数，我们只要和前面i-1个数相比找到比第i个数小且其解最大的值max，max+1就是第i个数的解！

// 最长上升子序列.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<memory.h>
using namespace std;
int a[1010]={0};
int len_[1010]={0};

int main()
{
	int n=0;
	int max_=0;
	while(scanf("%d",&n)!=EOF)
	{
		int i=0;
		max_=0;

		memset(a,0,sizeof(a));
		for(i=0;i<n;i++)
		{
			scanf("%d",&a[i]);
			len_[i]=1;
		}
		for(i=1;i<n;i++)
		    for(int j=0;j<i;j++)
				  if(a[i]>a[j])
				  {
					  len_[i]=max(len_[j]+1,len_[i]);
				  }
					 
	
		for(i=0;i<n;i++)
			if(len_[i]>max_)
				max_=len_[i];
		printf("%d\n",max_);
		
	}
	return 0;
}

经典动态规划问题--最长上升子序列 POJ--2533,布布扣,bubuko.com

经典动态规划问题--最长上升子序列 POJ--2533

原文：http://blog.csdn.net/linsheng9731/article/details/23862077