Es la vida~

Maximum subarray problem은 주어진 수열(Array) 중 연속된 수의 합(Sum of Sub array)의 최대값을 구하는 알고리즘이다.

예를 들어 다음과 같은 수열이 주어진 경우의 연속된 수의 합의 최대값은 6이다.

[−2, 1, −3, 4, −1, 2, 1, −5, 4]

이 알고리즘을 구현하기 위한 C 코드는 다음과 같다.

우선 본 페이지에서 소개하는 Maximum subarray problem을 풀기 위한 핵심은 다음과 같이 주어진 수열에서의 n-1과 n의 합의 배열을 이용한다.

#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;
  }
}