최대 부분 수열의 합 Maximum Subsequence Sum

• Ref. [M. Weiss, Data Structure and Algorithm Analysis in C (2nd ed.), Pearson, 1997. 2.4.3]

  • Given N (possiblly negative) A_0, A_1, ..., A_{N-1} \in \mathbb{Z}
  • find the maximum value of \sum_{k=i}^{j} {A_k } for 0 \leq i \leq j \leq N-1
  • for convenience, the max subseuqence sum is 0 if all the integers 're <0

• Example

  • (-2, 11, -4, 13, -5, -2). → MSS = 20

    

• Maximum Subarray Problem

• Maximum Positive Sum Subarray Problem

• Max. Sum Subsequence versus Max. Subsequence Sum

• 길이 $n$인 정수의 수열 a_0, a_1, ..., a_{n-1} 이 입력으로 주어져 있다.

• 여기서 부분 수열 [i, j]라는 것은 a_i, a_{i+1}, a_{i+2}..., , a_{j} 를 말한다.

• 본 문제는 주어진 수열의 부분 수열의 합,즉 \sum_{i \leq k \leq j} {a_k} 의 최대값을 구하는 문제이다. (이때 주어진 수열의 정수가 모두 음수이면 최대 부분 수열의 합은 0 이라고 간주한다)

  • 예를 들어 다음과 같은 수열이 주어졌을 때, + 31, −41, +59, +26, −53, +58, +97, −93, −23, +84 최대 부분 수열은 $[2,6]$이며 수열의 합은 187 이 된다.

• 이 문제는 최대 부분 수열의 합을 구하는 것이지만, 앞으로 소개할 알고리즘을 조금만 수정하면 최대 부분 수열도 쉽게 구할 수 있다.

  Algorithm1 : 모든 경우의 수 찾기 - O(N^3) Algorithm2 : Sum구할 때 중복 조금 피하기 - O(N^2) Algorithm3 : Divide n Conquer - O(N log N) Algorithm4 : Dynamic Programming - O(N)

  • 

• Strategy

  • Enumerate all possibilities one at a time.

  • No efficiency is considered, resulting in a lot of unnecessary computation!

    Maxsum = 0
    for (i=0; i < n; i++){
        for (j=i; j < n; j++){
            Thissum = sum(A[i:j])
          	Maxsum = max(Thissum, Maxsum)
        }
    }

  • 모든 경우의 수를 하나하나 모두 따져보는 방법.

    int MaxSubsequenceSum(const int A[], int N){
    int ThisSum, MaxSum, i, j, k;
      //i = 리스트 왼쪽 끝 인덱스, j = 리스트 오른쪽 끝 인덱스, ThisSum = 고려 대상 부분 리스트 합, MaxSum = 문제 최종결론
    MaxSum = 0;
    for (i = 0; i < N; i++)
        for (j = i; j < N; j++)
        {
            ThisSum = 0;
            for (k = i; k <= j; k++)
                ThisSum += A[k];
            if (ThisSum > MaxSum)
                MaxSum = ThisSum;
        }
    return MaxSum;
    }
    

  • Is this for-loop OK for you?

  • Time Complexity : O(N^3)

    • 𝑖와 관련된 반복문은 𝑛n번, 𝑗와 관련된 반복문은 최대 𝑛번, Thissum을 구할 때 최대 𝑛개의 요소를 계산해야 하기에
    • \sum_{i=0}^{N-1} \sum_{j=i}^{N-1} \sum_{k=i}^{j} 1 = \frac{N^3 + 3N^2 + 2N}{6}
    • \sum_{j=i}^{N-1}\ (j-i+1) = \frac{(N-i+1)(N-i)}{2}
    • \sum_{k=i}^{j} 1 = j-i+1

• Strategy

  • Get rid of the inefficiency in the innermost for-loop. Algorithm 1보다 중복을 줄이는 방법

  • Maxsum = 0
    for (i=0; i < n; i++){
          for (j=i; j < n; j++){
              Thissum = sum(A[i:j])
            	Maxsum = max(Thissum, Maxsum)
            }
        }

    • Notice that \sum_{k=i}^{j } {A_k} = A_j + \sum_{k=i}^{j-1} {A_k}

    • int MaxSubsequenceSum(const int A[], int N)
      {
        int ThisSum, MaxSum, i, j;
        MaxSum = 0;
      for (i = 0; i < N; i++){
        ThisSum = 0;
        for (j = i; j < N; j++){
            ThisSum += A[j];
          if (ThisSum > MaxSum)
            MaxSum = ThisSum;
        }
      }return MaxSum;

    }

  • time complexity : O(N^2)

• Strategy

  • Use the Divide-and-Conquer strategy.

    • 원 문제를 작은 문제로 나눠 풀고, 그 결과를 합쳐 문제를 해결하는 알고리즘

  • The maximum subsequence sum can be in one of three places.

    int MaxSubSum(const int A[], int Left, int Right){
    int MaxLeftSum, MaxRightSum;
    int MaxLeftBorderSum, MaxRightBorderSum;
    int LeftBorderSum, RightBorderSum;
    int Center, i;
      //종료조건
    if (Left == Right){
        if (A[Left] > 0)
    				return A[Left];
        else
            return 0;
    }
    //divide n conquer 
    Center = (Left + Right) / 2;
    //왼쪽, 오른쪽, 중간
    MaxLeftSum = MaxSubSum(A, Left, Center);
    MaxRightSum = MaxSubSum(A, Center + 1, Right);
    MaxLeftBorderSum = 0;
    LeftBorderSum = 0;
    
    //1. left ending 끝으로 하는 mss
    for (i = Center; i >= Left; i--){
        LeftBorderSum += A[i];
        if (LeftBorderSum > MaxLeftBorderSum)
            MaxLeftBorderSum = LeftBorderSum;
    }
    MaxRightBorderSum = 0;
    RightBorderSum = 0;
    //2. right ending 시작으로 하는 mss
    for (i = Center; i <= Right; i++){
        RightBorderSum += A[i];
        if (RightBorderSum > MaxRightBorderSum)
            MaxRightBorderSum = RightBorderSum;
    }
    return Max3(MaxLeftSum, MaxRightSum, MaxLeftBorderSum + MaxRightBorderSum);
    }
    int MaxSubsequenceSum(const int A[], int N) { 
    	return MaxSubSum(A, 0, N - 1); 
    }
    

• cost : T(n) = 2T(n/2) + cn, T(1) = d

• why O(N log N) ?

  • T(n) = 2T(\frac n 2) + cn, T(1) = d $ = 2 [ 2T(\frac n {2^2}) + c \frac n 2 ] + cn$ = 2^2 T [ \frac n {2^2}] + 2cn = 2^3 T [ \frac n {2^3}] + 3cn =... = 2^i T [ \frac n {2^i}] + icn = 2^{log_2 n} T(1) + log_2 n \cdot cn =nT(1) + log_2 n \cdot cn = O(n) + O(n log_2 n) = O(n log_2 n)

• Strategy

  • Use the Dynamic Programming strategy.

  • subsequence sum<0인 경우, 논리적으로 최대값이 될 수 없음에 착안한 전략

  • 만약에 sum이 음수라도 무방하고 1개 이상의 원소로 구 성된 Subsequence (subarray)를 구하는 문제라면?

    int MaxSubsequenceSum(const int A[], int N){
        int ThisSum, MaxSum, i;
    
        ThisSum = 0; MaxSum = 0;
        for(i = 0; i < N; i++){
            ThisSum += A[i];
            if(ThisSum > MaxSum)
                MaxSum = ThisSum;
            else if(ThisSum < 0)
                ThisSum = 0;
        }
        return MaxSum;
    }

  • Time Complexity : O(n)

    • for i, iteration n times, and O(1) for 1 calculation

  • C Implementation

    • Maximum sum rectangle in a 2D matrix (DP-27) by GeeksforGeeks

int kadane(int *arr, int *start, int *finish, int n)
{
    int sum = 0, maxSum = INT_MIN;

    *finish = -1;
    int local_start = 0;
    for (int i = 0; i < n; ++i)
    {
        sum += arr[i];
        if (sum < 0)
        {
            sum = 0;
            local_start = i + 1;
        }
        else if (sum > maxSum)
        {
            maxSum = sum;
            *start = local_start;
            *finish = i;
        }
    }
    if (*finish != -1)
        return maxSum; 
    // at least one non-negative number.
    
    // When all numbers in the array are negative
    maxSum = arr[0];
    *start = *finish = 0;
    for (int i = 1; i < n; i++)
    {
        if (arr[i] > maxSum)
        {
            maxSum = arr[i];
            *start = *finish = i;
        }
    }
    // Empty subsequence를 허용하면 0을 리턴 (원래 문제)
    // Empty subsequence를 허용하지 않으면 음수 중 가장 큰 원소를 리턴
    return maxSum;
}