BOJ 1912 연속합

문제출처 : https://www.acmicpc.net/problem/1912

1. 문제요약

- n개로 이루어진 임의의 수열 중 연속되는 숫자 합의 최대값은?

- A = {10, -4, 3, 1, 5, 6, -35, 12, 21, -1}

  A = {10, -4, 3, 1, 5, 6, -35, 12, 21, -1} 12 + 21 연속합이 33으로 최대

- 1 <= n <= 100,000

  -1,000 <= Ai <= 1,000

2. 접근방법

- 연속합이 최대

- 어느지점에서 새로운 연속이 생길까?

- 이전 까지의 합 보다 현재의 값이 더 크면 새로운 연속의 시작

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

a	10	-4	3	1	5	6	-35	12	21	-1
d	10	0	0	0	0	0	0	0	0	0

a	10	-4	3	1	5	6	-35	12	21	-1
d	10	6	0	0	0	0	0	0	0	0

a	10	-4	3	1	5	6	-35	12	21	-1
d	10	6	9	0	0	0	0	0	0	0

a	10	-4	3	1	5	6	-35	12	21	-1
d	10	6	9	10	0	0	0	0	0	0

a	10	-4	3	1	5	6	-35	12	21	-1
d	10	6	9	10	15	0	0	0	0	0

a	10	-4	3	1	5	6	-35	12	21	-1
d	10	6	9	10	15	21	0	0	0	0

a	10	-4	3	1	5	6	-35	12	21	-1
d	10	6	9	10	15	21	-14	0	0	0

a	10	-4	3	1	5	6	-35	12	21	-1
d	10	6	9	10	15	21	-14	12	0	0

a	10	-4	3	1	5	6	-35	12	21	-1
d	10	6	9	10	15	21	-14	12	33	0

a	10	-4	3	1	5	6	-35	12	21	-1
d	10	6	9	10	15	21	-14	12	33	32

3. 시간복잡도

- n

4. 회고

- 값의 범위가 -1000 <= Ai <= 1000 으로 음수가 됨을 망각함.

- 첫번째 실수, d의 값을 0으로 시작함..

  첫번째 입력값이 음수이면 d는 음수가 아니라 0으로 시작하게 됨

- 두번째 실수, ans의 값을 0으로 초기화함...

  집합의 모든 수가 음수 이면 정답은 0이 되어버림

소스코드

#include<iostream>
using namespace std;

int n, temp, d = -1001, ans = -1001;

int main(void){
	cin >> n;
	for (int i = 1; i <= n; i++){
		cin >> temp;
		if (temp < d + temp) d = d + temp;
		else d = temp;
		if (ans < d) ans = d;
	}
	cout << ans << "\n";
	return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]