1912
BOJ 1912 연속합
boj 1912 연속합 간단한 DP 문제이다. a[i]는 수열이 담긴 배열이고, 테이블로 D[i]는 i번째 원소를 마지막으로 하는 연속된 수열 합의 최댓값이라고 정의한다. 합이므로 초기 값은 원소 자기 자신의 값이다. 그러므로 D[i] = a[i]로 초기화한다. 수열이 연속된다는 것을 인지하면 D[i] = max(D[i], D[i-1] + a[i]) 이라는 점화식이 쉽게 만들어진다. 각 수는 -1000에서 1000 사이이 수 이므로 ans는 초기 값으로 -1001을 주었다. 위 내용을 바탕으로 코드를 구현해보자. #include #include using namespace std; int n; int a[100005]; int D[100005]; int ans = -1001; int main(void) ..