동적 계획 - - 최장 상승 하위 시퀀스

이것은 고전적인 LIS(즉 최장 상승 서열) 문제입니다. 가능한 한 좋은 해법을 설계하여 서열의 최장 상승 서열의 길이를 구하십시오.
시퀀스 A와 그 길이 n (길이가 500보다 작음) 을 지정하면 LIS의 길이를 되돌려 주십시오.
길이가 n인 서열 dp를 만듭니다. dp[i]는 A[i]로 끝나는 하위 서열 중 A[0,......i]로 늘어나는 하위 서열의 길이를 나타냅니다.
왼쪽에서 오른쪽으로 서열 A를 훑어보고 모든 단어로 끝나는 서열에 기록한다. 가장 긴 서열의 길이를 상승한 다음에 가장 큰 값을 찾아내는 것이 우리가 필요로 하는 값이다.각 자모에 대응하는 하위 서열의 최단 길이는 1이기 때문이다.그래서 dp의 모든 값을 1로 초기화합니다.dp[i]를 계산할 때 A[i]가 이전에 그보다 작은 수를 찾아낸다. 그보다 작은 수는 모두 A[i]로 끝나는 상승 서열의 밑바닥 두 번째 값으로 할 수 있기 때문에 그 중에서 dp[j]가 가장 큰 값을 이 상승 서열의 밑바닥 두 번째 값으로 선택한다.dp[i]=dp[j]+1;

int getLIS(vector A, int n) {
	  int * dp=new int[n];
	  for (int i = 0; i < n; i++)
	  {
		  dp[i] = 1;
	  } 
	  for (int i = 1; i < n; i++)
	  {
		  int max = 0;
		  for (int j = 0; j < i; j++)
		  {	 
			  if (A[i] > A[j])// A[i]        ，  A[i]                1       
				  max = max > dp[j] ? max : dp[j];	
		  }
		  dp[i] = max + 1;
	  }
	  int a = 0;
	  for (int j = 0; j < n; j++)
	  {
		  if (a < dp[j])
			  a = dp[j];
	  }
	  return a;
  }