개요
-
입력
입력 파일의 첫 번째 줄에 테스트 케이스의 수를 의미하는 자연수 T가 주어진다. 그 다음에는 T개의 테스트 케이스가 주어진다.각 테스트케이스 별로 첫 번째 줄에 배열의 크기 N이 주어진다. (1 ≤ N ≤ 1,000)
그리고 두 번째 줄에 배열 X의 내용을 나타내는 N개의 정수가 공백으로 구분되어 주어진다. 이때 주어지는 수는 절댓값이 1,000보다 작은 정수이다.
-
출력
각 테스트케이스 별로 maximum subarray의 합을 줄로 구분하여 출력한다.
접근방식
처음에 접근한 방식
-
부분배열의 합을 미리 Sum배열을 선언하여 입력값을 받을때 바로바로 저장을 해준다면
부분배열의 합을 계산할때 빠르게 가능하다.for (int i = 0; i < T; i++) { cin >> N; for (int j = 0; j < N; j++) { cin >> inputArr[j]; //Sum[i+1]배열은 i번째 까지의 합 Sum[j + 1] = Sum[j] + inputArr[j]; } -
그냥 브루트포스 방식으로 , 부분배열의 합을 다 구해놓은 뒤,
몇번째 배열에서 몇번째 배열을 뺐을 때 가장 큰지 구하는 식으로 구현하였다.//0부터 N까지의 index내에서 최대 부분배열 찾는 함수 int Solution() { if (N == 1) return Sum[1]; //싹다 음수일수도있으므로 최소값 0으로 잡으면 안 될듯 int maxSum= -1'000'001; // 첫번째 원소를 포함헤야하므로 0부터 시작해서 인덱스N까지 포함해야함 for (int i = 0; i < N; i++) { for (int j = i+1; j < N+1; j++) { maxSum = maxSum> Sum[j] - Sum[i]? maxSum: Sum[j]-Sum[i]; } } return maxSum; }
0번째 인덱스부터 다 더해가며 음수면 0으로 초기화하며 최대값 구하는 방식
하지만 위와 같은 방식이면, 케이스가 커지게되면 시간초과가 나는 방식이다.
따라서 테케당 O(N)의 시간복잡도를 유지하려면
int Solution() {
//싹다 음수일수도있으므로 최소값 0으로 잡으면 안 될듯
int maxSum= -1'000'001, tmpSum=0;
if (isAllElemNeg) {
for (int i = 0; i < N; i++) {
maxSum = maxSum > inputArr[i] ? maxSum : inputArr[i];
}
}
else {
// 어차피 연속된 합이 음수가 아닌이상 최대값임
for (int i = 0; i < N; i++) {
tmpSum += inputArr[i];
//만약 더했는데 음수가나오면 최대값이 될수없으므로 0으로 초기화
if (tmpSum < 0) tmpSum = 0;
//매번 비교해서 최대값 갱신
maxSum = maxSum > tmpSum ? maxSum : tmpSum;
}
}
return maxSum;
} 이런식으루 모든 원소가 음수인지 체크하는 isAllElemNeg변수로 체크 한 후,
모든 원소가 음수라면 제일 큰 원소 출력하고, 아니라면 차례대로 더하면서
음수면 0으로 초기화하고 다시 더하는 방식으로 최대 부분수열값 출력한다.
다이나믹 프로그래밍을 통한 방식
바로 위의 방식과 비슷하게 다이나믹 프로그래밍 방식으로도 풀 수 있는데,
각 dp배열마다 이전 단계의 최대합에 이번 원소 더한값과, 이번원소값만 비교해서
최대값 갱신하며 푸는 방식이다.
매번 비교할때마다 현재까지의 최대값 갱신해주면 답이 된다.
for (int j = 0; j < N; j++) {
cin >> inputArr[j];
dp[j + 1] = max(dp[j] + inputArr[j], inputArr[j]);
maxSum = max(maxSum, dp[j + 1]);
}첫 번째 방식 코드
#include<iostream>
using namespace std;
int inputArr[1001];
int Sum[1002];
int T = 0, N = 0;
//0부터 N까지의 index내에서 최대 부분배열 찾는 함수
int Solution() {
if (N == 1) return Sum[1];
//싹다 음수일수도있으므로 최소값 0으로 잡으면 안 될듯
int maxSum= -1'000'001;
// 첫번째 원소를 포함헤야하므로 0부터 시작해서 인덱스N까지 포함해야함
for (int i = 0; i < N; i++) {
for (int j = i+1; j < N+1; j++) {
maxSum = maxSum> Sum[j] - Sum[i]? maxSum: Sum[j]-Sum[i];
}
}
return maxSum;
}
void Input() {
cin >> T;
for (int i = 0; i < T; i++) {
cin >> N;
for (int j = 0; j < N; j++) {
cin >> inputArr[j];
//Sum[i+1]배열은 i번째 까지의 합
Sum[j + 1] = Sum[j] + inputArr[j];
}
cout<<Solution()<<'\n';
}
}
int main() {
Input();
}두 번째 방식 코드
#include<iostream>
using namespace std;
int inputArr[1001];
int T = 0, N = 0;
//모든 원소 음수인지
bool isAllElemNeg = true;
//0부터 N까지의 index내에서 최대 부분배열 찾는 함수
int Solution() {
//싹다 음수일수도있으므로 최소값 0으로 잡으면 안 될듯
int maxSum= -1'000'001, tmpSum=0;
if (isAllElemNeg) {
for (int i = 0; i < N; i++) {
maxSum = maxSum > inputArr[i] ? maxSum : inputArr[i];
}
}
else {
// 어차피 연속된 합이 음수가 아닌이상 최대값임
for (int i = 0; i < N; i++) {
tmpSum += inputArr[i];
//만약 더했는데 음수가나오면 최대값이 될수없으므로 0으로 초기화
if (tmpSum < 0) tmpSum = 0;
//매번 비교해서 최대값 갱신
maxSum = maxSum > tmpSum ? maxSum : tmpSum;
}
}
return maxSum;
}
void Input() {
cin >> T;
for (int i = 0; i < T; i++) {
isAllElemNeg = true;
cin >> N;
for (int j = 0; j < N; j++) {
cin >> inputArr[j];
if (inputArr[j] > 0) isAllElemNeg = false;
}
cout<<Solution()<<'\n';
}
}
int main() {
Input();
}세번째 방식 코드
#include<iostream>
#include<algorithm>
using namespace std;
int inputArr[1001];
int dp[1002];
int T = 0, N = 0, maxSum = -1'000'001;
void Input() {
cin >> T;
for (int i = 0; i < T; i++) {
maxSum = -1'000'001;
cin >> N;
for (int j = 0; j < N; j++) {
cin >> inputArr[j];
dp[j + 1] = max(dp[j] + inputArr[j], inputArr[j]);
maxSum = max(maxSum, dp[j + 1]);
}
cout<<maxSum<<'\n';
}
}
int main() {
Input();
}문풀후생
첫번째 방식에선 인덱스 N을 포함시켜줘야 해서 j의 인덱스를 i+1부터 N까지 설정해줘야한다.
두번째 방식으로 푸는 과정에선 isAllElemNeg변수를 매 실행 마다 초기화를 안시켜줘서 많이 헤멨다.
