백준 10211 c++ "Maximum Subarray" -PlusUltraCode-

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

 

[필자 사고]

필자는 이 문제를 DP를 이용하여 해결했다.

점화식은 다음과 같다.

DP[i] = 과거부터 i번째까지 최대의 값을 저장해 놓는 값

즉 DP[i] = max(dp[i-1]+arr[i] , arr[i]) 를 설정하게 되면 과거부터 i번째까지 최대값과 현재 arr[i]의 최대값을 비교하는 거고

만약 arr[i]가 더 크다면 다시 시작점을 갱신하는 방법이다.

아래는 코드 해설이다.

[코드 해설]

2. 입력 처리 및 초기화 (Init 함수)

Init() 함수는 입력을 받아 배열과 DP 배열을 초기화하는 역할을 합니다.

1. dp 벡터와 arr 벡터를 비우고, 크기를 N+1로 설정합니다.
2. N개의 정수를 입력받아 arr 벡터에 저장합니다.
3. 첫 번째 값 arr[0]을 dp[0]에 저장합니다.

---

3. 연속 부분합 계산 (Game_Start 함수)

이 함수는 주어진 N개의 정수 배열에서 연속 부분 수열의 최대 합을 계산하는 역할을 합니다.

1. N을 입력받고 Init()을 호출하여 배열을 초기화합니다.
2. dp[i]를 다음과 같은 점화식을 기반으로 갱신합니다: dp[i]=max⁡(arr[i]+dp[i−1],arr[i])dp[i] = \max(arr[i] + dp[i - 1], arr[i])dp[i]=max(arr[i]+dp[i−1],arr[i]) 즉, 현재 원소를 이전 최대 부분합에 더할지, 단독으로 시작할지를 결정합니다.
3. maxNum 변수를 사용하여 최대 부분합을 지속적으로 갱신합니다.
4. 최종적으로 maxNum을 출력합니다.

이 알고리즘은 카데인 알고리즘(Kadane's Algorithm)으로, 시간 복잡도 O(N)의 효율적인 방식입니다.

[소스 코드]

#include <iostream>
#include <vector>
#include <cmath>
#include <climits>

using namespace std;

int T;
int N;
vector<int> dp;
vector<int> arr;
void Init() {
	dp.clear();
	arr.clear();
	arr.resize(N + 1);
	dp.resize(N + 1);

	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
	dp[0] = arr[0];
}

void Game_Start() {
	cin >> N;
	
	Init();

	int maxNum = arr[0];
	for (int i = 1; i < N; i++) {
		dp[i] = max(arr[i] + dp[i - 1], arr[i]);
		maxNum = max(dp[i], maxNum);
	}

	cout << maxNum << '\n';
}

int main(void) {
	int T;
	cin >> T;
	while (T--) {
		Game_Start();
	}
}