[c++/백준] 1912 연속합

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

1912번: 연속합

dp의 순서를 찾아준 후 최댓값을 따로 만들어서 풀어주었다. 생각보다 쉽게 풀었다. 

 

순서는 첫번째 빼고 (dp의 직전 값과 arr의 현재 값을 더해준 것, arr의 현재값)을 비교해서 더 큰 값을 dp에 넣어주면 된다. 

고려해야될 것은 계속하다보면 가장 큰 합이 구해졌는데 음수를 계속 더해서 작아지는 경우가 있다. 이런 경우를 대비하여 큰 수를 갱신할 maxCount값을 만들었다. 

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

int arr[100001];
int dp[100001];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int maxCount = -1001;	//최댓값 갱신하기 위함
	int n;
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
    
	dp[0] = arr[0];
	if (dp[0] > maxCount) {	//dp[0]일 때도 고려해주기
		maxCount = dp[0];
	}
	for (int i = 1; i < n; i++) {
		dp[i] = max(dp[i - 1] + arr[i], arr[i]);	//dp의 규칙
		if (dp[i] > maxCount) {	//최댓값 갱신
			maxCount = dp[i];
		}
	}
	cout << maxCount;
}

스스로의 힘으로 풀어서 개뿌듯,..이래서 코딩한다 ㅜ