인프런 커뮤니티 질문&답변

안녕하세요 stark님 ㅎㅎ

일단 이 문제의 해답로직은.

최적의 LIS를 구하고.

구할 때 해당 LIS의 가장 마지막 idx를 찾아서 retValue에 놓고 그걸 기반으로 trace를 해야겠죠?

자,그럼 stark님의 코드를 볼게요.

				if (cache[i] < cache[j] + 1)
				{
					cache[i] = cache[j] + 1;
					trace[arr[i]] = arr[j];
					retValue = arr[i];
				}
			}
		}
		ret = max(ret, cache[i]);

이부분이 틀린거 같은데요.

자, 뭐냐면요.

이 이 j번째를 사용해서 LIS를 만들어서 최적해라면 ~~ trace를 걸고, retvalue에 arr[i]를 넣죠?

근데 이 retValue는

	for (int i = retValue; i != 0; i = trace[i])

갑자기 마지막에 가장 큰 LIS의 마지막 value인양 들어가 있네요?

retValue는 최고의 LIS의 마지막이 되어야 하는 부분이 없지 않을까요?

그리고 질문 주실 때 질문 링킹 부탁드립니다.

강의 - 질문 하는 법 보시면 있어요 ㅎㅎ

감사합니다.