[백준 알고리즘] 1912번 연속합

문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

 

풀이

첫번째 수를 사용했을 때의 최댓값, 두번째 수를 사용했을 때의 최댓값, 세번째 수를 사용했을 때의 최댓값... 이렇게 진행 되는 것을 보면 해당 문제는 DP 문제로 생각할 수 있다.

 

다만 연속된 수 이기 때문에 N번째 수를 사용한다 했을 때에는 경우의 수가 다음과 같이

 

1) N-1까지의 max 값과 N번째의 수

2) N번째의 수 : (N-1번째가 -1이라 감소할 수도 있으므로)

 

2가지가 나올 수 있다. 즉 점화식을 구성해 보면

 

1) DP[N-1] + Array[N]

2) Array[N]

 

으로 간단히 나타낼 수 있다.

 

#include<iostream>

using namespace std;

int Numarray[100000];
int maxNum[100000];

/*

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.
예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

*/
int max(int a, int b) {
	return a > b ? a : b;
}
int main() {
	
	int Num;
	cin >> Num;
	
	for (int i = 0; i < Num; i++) {
		int temp;
		cin >> temp;
		Numarray[i] = temp;
	}

	maxNum[0] = Numarray[0];
	
	for (int i = 1; i < Num; i++) {
		maxNum[i] = max(maxNum[i - 1] + Numarray[i], Numarray[i]);
	}

	
	int max = -100000000;
	for (int i = 0; i < Num; i++) {
		if (max < maxNum[i]) max = maxNum[i];

	}

	cout << max << endl;
	




}

 

 

마지막 예시를 통해 하나 생각 못한 것이 있는 데 해당 수열은 정수 이기 때문에 모든 수가 음수로 올 수도 있다.

그렇기 때문에  

 

int max = -100000000;

max값은 해당 값으로 초기화 하여 진행한다. ( 100,000 자리배열 이며 정수 최솟값은 -1,000 이기 때문이다.)

 

끝.