기시 알고리즘 설명: 제50문제 동적 기획의 차단 미사일

/*
  :    。       ，      <=     。           。   ，        ，                   。
  :      。   :    k(k<=25)。   :k   ，   k      ，     ，    
  :      ，      ，         。
  :
8
300 207 155 300 299 170 158 65
  :
6/
  ：             （                     ，  >=  ,  ）。     :
      F[1] = 1
	  F[i] = max{1,F[j]+1} | j < i && aj >= ai
  :
1              :      ，       ，         ，       ，     >=   ，                  ，  
         
2        ，              1，                 
3   ，     iMax = 1        ，  i         。       :       &  
4       O(n*n),      O(n)
5            :           ，          i             ，                             
    ，         。
*/

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#define N 26

int max(int a,int b)
{
	return a > b ? a:b;
}

int main(int argc,char* argv[])
{
	int iElemArr[N];//       
	int iLenArr[N];//    i                
	int n,iCnt = 1;
	int i,j;
	while(EOF!=scanf("%d",&n))
	{
		//      
		int iTemp = n;
		while(iTemp--)
		{
			scanf("%d",&iElemArr[iCnt++]);
		}
		//int iMax= 1;
		//         
		for(i = 1 ; i <= n ; i++)
		{
			//  ，        iMax    i     
			int iMax = 1;
			//           
			for(j = 1; j < i ; j++)
			{
				//       >=     ，     i            
				if(iElemArr[j] >= iElemArr[i])
				{
					iMax = max(iMax,iLenArr[j] + 1);
				}
			}
			iLenArr[i] = iMax;//    i            
		}
		int iMMax = -123123123;
		for(i = 1 ; i <= n ; i++)
		{
			if(iLenArr[i] > iMMax)
			{
				iMMax = iLenArr[i];
			}
		}
		printf("%d
",iMMax);
	}
	system("pause");
	getchar();
	return 0;
}