Maximum Subarray(백준 10211번)
dynamic programming과 brute force알고리즘이 활용되는 문제이다.
우선 문제를 살펴보면 크기가 n인 배열에 원소의 합이 가장 큰 부분수열을 찾는 문제이다.
처음엔 접근을 두포인터로 접근하여 값들의 합중 가장 큰 값을 답으로 하고자 하였으나
문제에서 요구한 시간을 충족시키지 못할것 같아 다른 방법을 모색하였다.
그 결과 다이나믹 프로그래밍을 적용하게 되었다.
먼저 배열의 값이 들어갈 배열을 만들어 주고 dp(다이나믹 프로그래밍)의 값이 들어갈 배열을 만들어주었다.
for문을 1부터 진행하면서 배열에 들어오는 값들을 순차적으로 비교해준다.
dp에 넣을 값들을 비교해준다.
dp[1] = max(dp[0] + arr[1], arr[1]);
dp[2] = max(dp[1] + arr[2], arr[2]);
.
.
.
만약 값으로 -999, 998, 5가 들어갔다고 하자.
그러면 dp[1]에는 -999가 들어가있다.
dp[2]에는 -999 + 998 과 998중 큰 값이 저장된다.
이때 998이 더 크기때문에 998로 Maximum Subarray가 변경이 된다.
그리고 dp[3]에는 998 + 5와 5중 큰 값인 998 + 5 = 1003이 저장이 되고
Maximum Subarray의 값은 1003이 된다.
소스코드 :
#include <iostream>
using namespace std;
int dp[1001] = {0, };
int arr[1001] = {0, };
int main() {
ios_base::sync_with_stdio(NULL);
cin.tie();
cout.tie();
int t, n;
cin >> t;
while (t--) {
cin >> n;
int answer = -999999999;
for (int i = 1; i <= n; i++) {
cin >> arr[i];
dp[i] = max(dp[i-1] + arr[i], arr[i]);
answer = max(answer, dp[i]);
}
cout << answer << "\n";
}
}
Author And Source
이 문제에 관하여(Maximum Subarray(백준 10211번)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jiho9702/Maximum-Subarray백준-10211번저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)