[BOJ/1912] 연속합

(공감과 댓글 하나는 글쓴이에게 큰 힘이 됩니다.)

 

문제 링크

- https://www.acmicpc.net/problem/1912

 

사용 알고리즘

- DP

 

풀이

- d[i] = a[i]를 가장 마지막으로 하는 가장 큰 연속합

- d[i] = max(d[i - 1] + a[i], a[i])

 

소스 코드

- https://github.com/moomini/algorithm/blob/master/boj/1912.cpp

#include <cstdio>   int d[100003]; int a[100003];   int main(void) {     int n; scanf("%d", &n);     int ans = -100000003;     for (int i = 1; i <= n; ++i) {         scanf("%d", &a[i]);         d[i] = (a[i] > (d[i - 1] + a[i])) ? a[i] : d[i - 1] + a[i];         if (ans < d[i]) ans = d[i];     }     printf("%d\n", ans);     return 0; } Colored by Color Scripter

cs