백준 가장 긴 증가하는 부분 수열 4 14002

문제설명 :

이것은 '역추척'기법이 필요한 문제이다 lcs2 풀기전에 이것을 통해 배우고 lcs2를 풀겠습니다 .

문제 풀이 :

역추적을 할려면 일단 바로전의 위치를 저장할 배열을 만들어줘야한다
ex :b[1001]에 역추척 위치를 저장하겠습니다

1) 디피가 갱신될때 b에도 그 바로 직전의 idx도 넣는다

for(int i = 0 ; i < n; ++i)
    if(a[i] < a[k] && i < k) {
    if(dp[k] < 1 + solve(i)) {
        dp[k] = solve(i) + 1;
        b[k] = i     

에서 b[k] = i에 이 부분이 현재 k번째를 보는데 갱신 되는 i번째를 넣는 것이다.
더 긴 부분들을 차례 차례 들어간다

이것을 이용해서
while문을 이용해서 차례 차례 찾아가면된다

while(maxIdx >= 0) {

    v.push_back(a[maxIdx]);
    maxIdx = b[maxIdx];           // b에는 가장 긴 부분 수열의 idx 바로 직전 값들이 들어있다  

}