크기가 1씩 증가하는 가장 긴 증가하는 부분수열의 길이를 구하는 다이나믹 프로그래밍

15966번: 군계일학 주어진 배열에서 ai = a1 + (i-1)을 만족하는 부분 수열 a의 길이의 최댓값을 구하는 문제 -------------------------------------------------------------------------------------------------------------------------------------------------- 그런데 가장 긴 증가하는 부분 수열을 찾는거니까 O(N^2)인가? 근데 N이 10만인데? 그러면 O(N)에 찾을 수 있다는건가? 한참 고민했다.. 갑자기 번뜩이는?아이디어가 떠올랐다 먼저 핵심은 ai = a1 + (i-1)을 만족하는 수열은 무엇을 의미하는가? a1 = 1이면 a2 = 2, a3 = 3,.... a1 = 2이..