이미 존재하는 20이 들어오면 20의 자리를 대체한다.
존재하지 않는 25가 들어오면 30을 대체한다. 격차가 작아져야 LIS 수열이 더 길어질 수 있다.
Code
const solution = function (i) {
const [N, ...A] = i.toString().trim().split(/\s+/).map(Number);
const DP = Array(N + 1).fill(1);
for (let i = 0; i < N; i++) {
for (let j = 0; j < i; j++) {
if (A[j] < A[i] && DP[j] + 1 > DP[i]) {
DP[i] = DP[j] + 1;
}
}
}
console.log(Math.max(...DP));
return Math.max(...DP);
};
describe('가장 긴 증가하는 부분수열', () => {
it('TC1', () => {
expect(
solution(`6
10 20 10 30 20 50`)
).toStrictEqual(4);
});
});
TypeScript
복사
