<백준 알고리즘> 10211번: Maximum Subarray

문제

크기 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;
}