문제 링크https://www.acmicpc.net/problem/17216 문제 요약주어진 수열 \(A\)에서 합이 가장 큰 감소하는 부분 수열을 찾는 문제이다. 문제 풀이감소하는/증가하는 부분 수열을 찾는 문제는 전형적인 동적 계획법(Dynamic Programming) 문제들 중 하나이다. 이 문제 역시 점화식을 세워 동적 계획법으로 문제를 해결할 수 있다. 점화식을 세우기 전에 DP 배열부터 정의를 해보자. \(dp[i]\)는 수열 \(A\)에서 \(A[i]\)로 끝나는 감소 부분 수열의 합 중에서 가장 큰 값을 저장하는 배열이다. 그다음으로 DP 배열을 초기화한다. 각 원소는 자기 자신만을 포함하는 감소 부분 수열이 될 수 있으므로, \(dp[i]\)의 초기값을 \(A[i]\)로 설정한다. 이제..
