[백준] 1912번 연속합

1912번: 연속합

수열의 i번째의 위치에 있을 때 num[i]에

max(i번째의 값, i-1번째까지의 최댓값 + i번째의 값)

을 넣어주면 i번째까지의 최댓값이 저장된다.

 

여기서 i번째까지의 최댓값이 무조건 답이 아니기 때문에

Max를 만들어 계속 최댓값을 비교하여 찾아주고 출력하면 된다.

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	int N, num[100001] = { 0 }, Max;
	cin >> N >> num[0];
	Max = num[0];

	for (int n = 1; n < N; n++) {
		cin >> num[n];
		num[n] = max(num[n], num[n] + num[n - 1]);
		Max = max(Max, num[n]);
	}

	cout << Max;
    
	return 0;
}