백준 1912문제.

연속합 문제

 

---

Problem?

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

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

 

즉, 최대합을 만들자

 

Input

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

 

Output

첫째 줄에 답을 출력한다.

 

Solution

DP(Dynamic Programming) 문제 중 하나

 

가정 A(n) : input 배열 SUM(n) : n번째의 값이 포함된 연속된 임의의 수 배열의 최댓값 max_num : 그 전까지 경우를 모두 포함한 최댓값 (우리가 원하는 답)

 

SUM(n)을 구하는 방법은 "SUM(n-1) + A(n)"과 "A(n)" 중에서 큰 값을 고르면 된다.

 

max_num을 구하는 방법은 그 전의 max_num과 SUM(n) 중에서 큰 값을 고르면 된다.

 

Code

#include <iostream>
using namespace std;

#define COUNT_MAX 100001

int max(int a, int b) {
	if (a >= b)
		return a;
	return b;
}

int main(void) {
	int N;
	int A[COUNT_MAX];
	int SUM[COUNT_MAX];
	int max_num;

	cin >> N;
	for (int i = 1; i <= N; i++) {
		scanf("%d", &A[i]);
	}

	SUM[1] = A[1];
	max_num = A[1];

	for (int i = 2; i <= N; i++) {
		SUM[i] = max(SUM[i - 1] + A[i], A[i]);
		max_num = max(max_num, SUM[i]);
	}
		
	cout << max_num << endl;

	return 0;
}

 

---

오랜만에 코딩을 다시 시작해서 어려운 점이 많다.

 

하루에 하나씩 문제 푸는게 목표