백준 누적합

[baekjoon 1912] 연속합 - DP(동적 프로그래밍) (C++)

www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 문제는 주어진 수열에서 연속으로 나열된 숫자의 합이 최대가 되는 경우(결괏값은 합의 최댓값)를 찾는 것이다. 점화식을 세우기 위해서 여러 케이스를 생각해보았다. 일단 합의 최댓값이 되려면 더해지는 수가 음수면 안될 것 같았다. -> 하지만 이 i번째 음수를 포함하고 i+1번째 수를 더해서 최댓값이 나올 수 있다. -> i+1을 더해서 최댓값이 성립되려면 i번째까지의 누적합이 양수인 경우다. (i번째 누적합이 음수일 경우 ..