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

백준 1912

알고리즘 분류 : dynamic programming (동적 계획법)

정수로 이루어진 임의의 수열에서 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중, 가장 큰 합을 구하는 문제다.

먼저, 입력받은 수열을 저장하는 배열 arr과 각 위치에서의 최대 합을 저장하는 배열 dp를 선언한다. (이때 크기는 모두 100,001으로 지정했는데, 이는 입력을 인덱스 값 0이 아닌, 1부터 받기 위함이다. 동적 계획법에서는 이렇게 풀어야 편한 경우가 종종 있는 것 같다.)

변수 maxnum을 arr[1]의 값으로 초기화한 후, 배열 dp를 완성한다. (maxnum을 습관적으로 0 또는 음수로 초기화하지 않도록 주의한다.)

dp[i]=max(dp[i-1]+arr[i],arr[i])
이는 직전까지의 연속합에 arr[i]를 더하는 경우와 arr[i]부터 새로운 합을 시작하는 경우 중, 그 값이 더 큰 경우를 dp[i]에 저장한다는 것을 의미한다.

maxnum은 dp[1]부터 dp[n]까지의 값들 중, 가장 큰 값을 저장하게 된다.

#include <iostream>
#include <algorithm>

using namespace std;
int arr[100001];
int dp[100001];

int main(){
	int n;
	cin >> n;
	
	for(int i=1; i<=n; i++){
		cin >> arr[i];
	}
	
	int maxnum=arr[1]; //maxnum을 arr[1]의 값으로 초기화
	for(int i=1; i<=n; i++){
		dp[i]=max(dp[i-1]+arr[i],arr[i]); //둘 중 더 큰 값을 dp[i]에 저장
		maxnum=max(maxnum,dp[i]);
	}
	
	cout << maxnum;
}