[BOJ/Silver 3] 백준 10211 Maximum Subarray(C++)

문제 링크

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

10211번: Maximum Subarray

 

문제

크기 N인 정수형 배열 X가 있을 때, X의 부분 배열(X의 연속한 일부분) 중 각 원소의 합이 가장 큰 부분 배열을 찾는 Maximum subarray problem(최대 부분배열 문제)은 컴퓨터 과학에서 매우 잘 알려져 있다.

여러분은 N과 배열 X가 주어졌을 때, X의 maximum subarray의 합을 구하자. 즉, max1 ≤ i ≤  j ≤ N (X[i]+...+X[j])를 구하자.

입력

입력 파일의 첫 번째 줄에 테스트 케이스의 수를 의미하는 자연수 T가 주어진다. 그 다음에는 T개의 테스트 케이스가 주어진다.

각 테스트케이스 별로 첫 번째 줄에 배열의 크기 N이 주어진다. (1 ≤ N ≤ 1,000)

그리고 두 번째 줄에 배열 X의 내용을 나타내는 N개의 정수가 공백으로 구분되어 주어진다. 이때 주어지는 수는 절댓값이 1,000보다 작은 정수이다.

출력

각 테스트케이스 별로 maximum subarray의 합을 줄로 구분하여 출력한다.

예제 입력 1

2
5
1 2 3 4 5
5
2 1 -2 3 -5

예제 출력 1

15
4

알고리즘 분류

• 누적 합

풀이

누적 합을 구하고, 각 구간마다 합을 비교하여 제일 합이 큰 구간의 합을 구해준다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 1001
#define LL long long
#define INF 1e12

using namespace std;
int T, N;
LL X[MAX];
LL Sum[MAX];
LL Answer;

void Settings() {
	Answer = -INF;
	for (int i = 1; i <= N; i++) {
		for (int j = i; j <= N; j++) {
			Answer = max(Answer, Sum[j] - Sum[i - 1]);
		}
	}
}

void Find_Answer() {
	cout << Answer << "\n";
}

void Input() {
	cin >> T;
	while (T--) {
		cin >> N;
		for (int i = 1; i <= N; i++) {
			cin >> X[i];
			Sum[i] = Sum[i - 1] + X[i];
		}
		Settings();
		Find_Answer();
	};
}

int main() {
	FASTIO
	Input();

	return 0;
}