반응형
Maximum subarray problem은 주어진 수열(Array) 중 연속된 수의 합(Sum of Sub array)의 최대값을 구하는 알고리즘이다.
예를 들어 다음과 같은 수열이 주어진 경우의 연속된 수의 합의 최대값은 6이다.
[−2, 1, −3, 4, −1, 2, 1, −5, 4]
| -2 | 1 | -3 | 4 | -1 | 2 | 1 | -5 | -4 |
이 알고리즘을 구현하기 위한 C 코드는 다음과 같다.
우선 본 페이지에서 소개하는 Maximum subarray problem을 풀기 위한 핵심은 다음과 같이 주어진 수열에서의 n-1과 n의 합의 배열을 이용한다.
| 수열 | -2 | 1 | -3 | 4 | -1 | 2 | 1 | -5 | -4 |
| 합 | -2 | -1 | -2 | 1 | 3 | 1 | 3 | -4 | -9 |
#define N (100) //100개의 수열인 경우
int array[N];
int sum = 0;
void maximumSubArrayProblem()
{
for (int i = 1; i <= N; i++)
{
scanf ("%d", num); // 수열 값 입력. 다른 방법으로 입력해도 무관.
if (sum > 0)
sum += num;
else
sum = num;
if (ans < sum)
ans = sum;
}
}
반응형
'프로그래밍' 카테고리의 다른 글
| strcmp(), strtok() (0) | 2020.10.08 |
|---|---|
| 삽입정렬 (Insertion Sort) (0) | 2020.08.21 |
| Merge sort (병합 정렬, 합병 정렬) (0) | 2020.08.01 |
| 구글은 소프트웨어를 어떻게 테스트하는가? (0) | 2020.05.26 |
| [C++] 디폴트 매개변수, default parameter (0) | 2019.08.14 |
