[1912] 연속합

• 입력: 정수개수 N( 1≤N≤100,000) , 이후 N개의 정수 Ai ( -1,000 ≤ Ai ≤ 1,000)
• 출력: 연속된 숫자들의 합 중 최댓값
• 소스코드
#define _CRT_SECURE_NO_WARNINGS #include <cstdio> #include <vector> using namespace std; int max(int a, int b) { return (a > b ? a : b); } int main() { int n, MAX; scanf("%d", &n); vector<int> dp(n), arr(n); for (int i = 0; i < n; i++) scanf("%d", &arr[i]); dp[0] = MAX = arr[0]; for (int i = 1; i < n; i++) { dp[i] = max(arr[i], dp[i - 1] + arr[i]); MAX = max(MAX, dp[i]); } printf("%d\n", MAX); return 0; }

dp[i]에 [0..i]까지의 연속된 숫자들의 합 중 최댓값을 저장해둔다. 

이때, 음수가 존재할 수 있으므로 dp[i - 1] + arr[i]와 arr[i]를 비교해 더 큰값을 저장해둔다. 이 기능이 연속된 합만 저장해주는 역할을 한다. 

• 문제 참고: https://www.acmicpc.net/problem/1912