LIS(Longest Increasing Subsequence) 구하는데 정확히는 Subsequence가 모두 붙어있는 수열(Substring)을 구하는 경우.
Codeforces Round #613 Div2. B - Just Eat It! 1000Pts. Problem - B - Codeforces codeforces.com LIS(Longest Increasing Subsequence) 구하는데 정확히는 Subsequence가 모두 붙어있는 수열을 구하는 경우. 수열은 v[1], v[2], ..., v[n], n=10만, v[x]는 [-10억,10억] 범위 1. 상태공간 정의 dp[x] = x번째 배열을 반드시 포함하는 최대값 2. 점화식 dp[x] = max(0, dp[x-1]) + v[x]; DP문제 자체는 쉬운데 한가지 조건이 있었으니 n개를 모두 포함하는 수열은 답에서 제외해야 했다. 그래서 나는 f(n-1)을 구하고 v[1]=0으로 만든 뒤 f(n)..
