[일간임무] - 가장 긴 증가하는 부분 수열

정렬을 해서 값이 변화할 때마다 체크해선 풀 수 없습니다. { 5, 3 } 은 가장 긴 증가하는 부분 수열이 { 5 }, { 3 } 뿐인데 정렬을 하면 { 3, 5 } 가 되고 가장 긴 증가하는 부분 수열의 크기가 2가 되어 오답이 됩니다.

입력으로 받은 전체 수열을 Iterate하는 것은 같습니다. { 9, 10, 11, 1, 2, 3, 4, 5 }가 있다면 iter = 9부터 iter = 5까지 검증을 할 것입니다. 

figure 1a

Elapsed time : 12min

백준은 대체로 기본을 다지는데 유용한 것 같습니다. dp을 어디에 활용하면 좋을지 고민을 많이 한 문제인데 정답을 찾는 것 조차 dp을 활용합니다.