문제
크기 N인 정수형 배열 X가 있을 때, X의 부분 배열(X의 연속한 일부분) 중 각 원소의 합이 가장 큰 부분 배열을 찾는 Maximum subarray problem(최대 부분배열 문제)은 컴퓨터 과학에서 매우 잘 알려져 있다.
여러분은 N과 배열 X가 주어졌을 때, X의 maximum subarray의 합을 구하자. 즉, max(1 ≤ 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 |
더보기
Solution
#include<stdio.h>
#include<stdlib.h>
int maximum_subarray(int *arr,int size)
{
int sum=0, max=arr[0];
for(int i=0;i<size;i++)
{
sum=arr[i]+sum>arr[i]?arr[i]+sum:arr[i];
max=max>sum?max:sum;
}
return max;
}
int main(void)
{
int T;
scanf("%d", &T);
for(int t=0;t<T;t++)
{
int N, *X=NULL;
scanf("%d", &N);
X=(int *)malloc(N*sizeof(int));
for(int n=0;n<N;n++)
scanf("%d", &X[n]);
printf("%d\n", maximum_subarray(X,N));
free(X);
}
return 0;
}
728x90
'백준 알고리즘' 카테고리의 다른 글
<백준 알고리즘> 20124번: 모르고리즘 회장님 추천 받습니다 (0) | 2020.12.14 |
---|---|
<백준 알고리즘> 11023번: 더하기 3 (0) | 2020.12.10 |
<백준 알고리즘> 2688번: 줄어들지 않아 (0) | 2020.12.06 |
<백준 알고리즘> 2670번: 연속부분최대곱 (0) | 2020.12.06 |
<백준 알고리즘> 2010번: 플러그 (0) | 2020.12.04 |