어떻게 풀었는가?
해당 문제의 포인트는 해당 지점을 j가 0~i까지 검사하는 것이다.
해당 코드와 같이 if data[j] < data[i]:
배열의 해당 값이 지금 검사하고 있는 값보다 작다면, 원래 가지고 있던 dp의 값과 더 작은 배열의 dp에+1한 값 중
더 큰 값을 대입한다.
왜 저렇게 풀어야 하는가?
문제의 접근방식은 dp[]를 만들고 해당 index값까지 배열이 있다고 가정했을 때, 해당 index까지의 가장 긴 수열 부분을 구하여 dp[index]값에 대입하는 방식이였다.
문제를 보았을 떄 dp로 풀어야 겠다는 감이 왔고, dp로 풀기 위해 작은 단위로 쪼개서 생각하였다.
왜 저 코드가 가능하지?
해당 index값까지 오면서 차례대로 값을 비교한 후, 현재의 값 보다 작다면 그 값은 증가 수열이 될 수 있다.
예를 들어, 현재 값이 30이고 검사하는 값이 10이라면 10 - 30으로 증가수열이 될 수 있다.
만약 10 인덱스에 해당하는 dp값에 10까지 배열이 있을 때의 최대 부분 수열 길이가 저장되어 있다면,
그 값에 +1 한 값을 dp 30에 해당하는 인덱스에 넣어주면 된다.
dp[index]는 data[0~index]까지의 배열 중, data[index]값이 맨 마지막에 자리하는 가장 긴 증가하는 부분수열을 담고 있는 것이다.
그렇기 때문에
이 코드가 가능한 것이다.
data[i] > data[j] -> 데이터 i를 배열의 처음부터 i바로 전까지 검사하며 그 값보다 크다면, dp[i] = max(dp[j]+1, dp[i])를 통해 그 중 가장 긴 값을 차지하게 된다.