백준 c++ 1912 "연속합" -PlusUltraCode-

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

 

 

 

 

 

 

 

 

 

[필자 사고]

연속합 문제이다.

 

시간복잡도를 측정하기 위해 문제에서 주어진  N의 크기를 본 결과 N=100000이다.

 

즉 시간복잡도 n^2 인 형태로 코드를 짜면 안된다.

 

잠시 고민해본 결과 다이나믹 프로그래밍이 떠올라 해당 코드를 작성했다.

 

필자는 Dynamic 이라는 배열을 만들었고 Dynamic의 들어가는 숫자는 arr의 숫자들 중

 

순서대로 합해서 최대가 되는 숫자들만 넣는 형식으로 정의했다.

 

[소스 코드]

 

 

#include<iostream>
#include <vector>
using namespace std;

int N;
vector<int> arr;
vector<int> Dynamic;
int maxNum = -111111;

void Input() {
	
	cin >> N;
	arr.resize(N);
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
}

void Solve() {

	Dynamic.resize(N);
	Dynamic[0] = arr[0];
	maxNum = arr[0];
	for (int i = 1; i < N; i++) {
		Dynamic[i] = max(Dynamic[i - 1] + arr[i], arr[i]);
		maxNum = max(maxNum, Dynamic[i]);
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	Input();
	Solve();
	cout << maxNum;
}