| 사례 1 | 사례 2 | 사례 3 | 일반규칙 |

선형 O(N) 알고리즘 (사례 2)

-------------------------------------------------------------
 int MaxSubsequenceSum( const int A[ ], int N )
       {      int ThisSum, MaxSum, j;
              ThisSum = MaxSum = 0;
               for( j = 0; j < n; j++ )
 ①                 {     ThisSum += A[ j ];
 ②                        if( ThisSum > MaxSum ) MaxSum = ThisSum;
 ③                        else if( ThisSum < 0 )    ThisSum = 0;
                       }
 ④          return MaxSum;
       }
------------------------------------------------------------- 

       <trace>

    A[]

=

4

-3

5

-2

-1

2

6

-12

2

 j 

=

0

1

2

3

4

 5

6

7

8

ThisSum

=

4

1

6

4

3

5

11

0

2

현재 부분합

MaxSum

=

4

4

6

6

6

6

11

11

11

최대 부분합

① 집합의 첫 번째 정수를 ThisSum과 더한다.
② ThisSum과 MaxSum을 비교한다. 만일 ThisSum이 크면, 이 정수를 최대부분합 MaxSum으로
    놓는다. 그렇지 않다면 MaxSum은 기존 값을 그대로 유지한다.
③ ThisSum이 0보다 작은지 비교해서 만일 0보다 작다면 값을 0으로 놓는다. 최대 부분합을 계산하기     위함이다.
    집합의 나머지 정수들도 위 ①,②,③과정을 되풀이한다.
④ 더 이상 정수가 없을 때에 for문을 멈추고 최대 부분합 MaxSum을 반환한다.