[BOJ] C/C++ 1912 "연속합"

# 풀이 

앞에서 부터, 차례로 값을 더해 온 값들 중 최대가 되는 값(tmp)과,  새로운 값(dp[i])를 비교하여,

더 큰 값을 tmp에 저장하여 출력

 

---

# 소스코드

#include <iostream>
#include <algorithm>
using namespace std;
long long arr[100001];
long long dp[100001];

int main() {
	int n;
	long long tmp;

	//input
	cin >> n;
	for (int i = 0;i <= n;i++) {
		cin >> arr[i];
	}

	//init
	dp[0] = arr[0];
	tmp = arr[0];

	//cal
	for (int i = 1;i < n;i++) {
		dp[i] = max(dp[i - 1] + arr[i], arr[i]);
		tmp = max(dp[i], tmp);
	}

	cout << tmp;
	return 0;
}

---

# 문제 출처

www.acmicpc.net/problem/1912

1912번: 연속합

---