Algorithm/문제풀이
[백준] 1912번: 연속합
manzoo
2019. 6. 13. 12:40
문제링크 : https://www.acmicpc.net/problem/1912
문제풀이
동적 계획법으로 쉽게 풀 수 있는 문제이다.
dp배열을 따로 만들어서, 각 자리까지의 최댓값을 저장한다.
소스코드
/* * 백준 1912번: 연속합 */ #include <iostream> #include <algorithm> using namespace std; #define MAX 100001 int arr[MAX]; int dp[MAX]; int main() { int n; cin >> n; for (int i = 0; i < n; i++) { cin >> arr[i]; } dp[0] = arr[0]; int max_sum = arr[0]; for (int i = 1; i < n; i++) { // (현재 값, 현재 값 + 이전까지의 최댓값) 중 더 큰 값 저장 dp[i] = max(arr[i], arr[i] + dp[i - 1]); if (dp[i] > max_sum) max_sum = dp[i]; } cout << max_sum; return 0; }