11053:가장 긴 증가하는 부분 수열

https://www.acmicpc.net/problem/11053

틀린 풀이

1. d[n]

   • 첫번째 ~ n번째 값 중,
   • 가장 큰 수

2. 10 20 10 30 20 50

   • d[0] = 0
   • d[1] = 10
   • d[2] = 20
   • d[3] = 20
   • d[4] = 30
   • d[5] = 30
   • d[6] = 50

3. d 배열의 값이 바뀔 때를 count

4. count 값이 답.

맞는 풀이

LIS 문제. 유명한 문제.

• d[i]

  • a[1] … a[i] 가 있을 때,
  • a[i]를 마지막으로 하는
  • 가장 긴 증가하는 부분 수열의 길이.
  • d[i]는 a[i] 가 반드시 포함

• ~ a[j] … a[i]

  • ~ a[j]길이 : d[j] —-> d[j] + 1

• d[i]

  • max( d[j] ) + 1

• a[j] 와 a[i]의 관계

  • a[j] < a[i]

  i			1     2     3     4     5     6 
a[i]		10    20    10    30    20    50 
d[i]     	 1     2     1     3     2     4         

d[4]를 예를들어,
d[4]는 처음에 1. 왜냐하면 자기 자신하나만 있으면 길이기 1이기 때문에.
a[3]을 봤더니, a[4]보다 작아. 증가하는 수열이기때문에 올 수 있어. 그럼, d[3] +1 = 2. 1보다 크기 때문에. d[4]=2
a[2]을 봤더니, a[4]보다 작아. 증가하는 수열이기때문에 올 수 있어. 그럼, d[2] +1 = 3. 2보다 크기 때문에 d[4] =3 
a[1]을 봤더니, a[4]보다 작아. 증가하는 수열이기때문에 올 수 있어. 그럼, d[1] +1 = 1. 3보다 작기 때문에 그대로