Maximum subarray problem

In computer science, the maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers which has the largest sum. For example, for the sequence of values −2, 1, −3, 4, −1, 2, 1, −5, 4; the contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6.

The problem was first posed by Ulf Grenander of Brown University in 1977, as a simplified model for maximum likelihood estimation of patterns in digitized images. A linear time algorithm was found soon afterwards by Jay Kadane of Carnegie-Mellon University (Bentley 1984).

출처: https://en.wikipedia.org/wiki/Maximum_subarray_problem

분할 정복과 동적 계획법을 공부할 수 있는 Maximum subarray problem (최대 구간 합 문제) 입니다.

분할 정복 풀이법은 배열을 절반으로 나눠서 좌측 부분의 최대합과 우측 부분의 최대합의 합과 그리고 정답(최대합)의 배열이 (좌측이나 우측) 한 쪽에서 시작해서 한 쪽에서 끝날 가능성을 고려하여 3가지 경우 중 최대값을 구하는 방법입니다. 

동적 계획 풀이법은 동적 계획법답게 중복해서 최소값을 구하는 부분 즉 계산할 필요가 없는 부분을 건너뛰어 (계산 결과를 재활용함으로써) 시간 복잡도를 줄이고 있습니다.

c++

#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#include <vector>
#include <ctime>
 
using namespace std;
 
vector<int> numbers;
int N;
 
 
int bruteForce()
{
    int ret = INT_MIN;
    for (int i = 0; i < N; i++)
    {
        int sum = 0;
        for (int j = i; j < N; j++)
        {
            sum += numbers[j];
            ret = max(ret, sum);
        }
    }
    return ret;
}
 
int divideAndConquer(int left, int right)
{
    if (left == right)
        return numbers[left];
 
    int leftMaxSum = INT_MIN;
    int rightMaxSum = INT_MIN;
    
    int middle = (left + right) / 2;
 
    int tempSum = 0;
    for (int i = middle; i >= left; i--)
    {
        tempSum += numbers[i];
        leftMaxSum = max(leftMaxSum, tempSum);
    }
    tempSum = 0;
    for (int i = middle + 1; i <= right; i++)
    {
        tempSum += numbers[i];
        rightMaxSum = max(rightMaxSum, tempSum);
    }
 
    int dividedMaxSum = max(divideAndConquer(left, middle), divideAndConquer(middle + 1, right));
 
    return max(leftMaxSum + rightMaxSum, dividedMaxSum);
}
 
//Kadane's algorithm
int dynamicProgramming()
{
    int ret = INT_MIN;
    int partialSum = 0;
 
    for (int i = 0; i < N; i++)
    {
        partialSum = max(partialSum, 0) + numbers[i];
        ret = max(partialSum, ret);
    }
 
    return ret;
}
 
int main() 
{
    //8000 numbers 
    ifstream fin("input.in");
 
    int a;
    while (fin >> a)
    {
        numbers.push_back(a);
    }
 
    N = numbers.size();
 
 
    clock_t start = clock();
 
    cout << "bruteForce : " <<  bruteForce() << " elapse time : ";
 
    clock_t end = clock();
    double time = double(end - start) / CLOCKS_PER_SEC;
    cout << time << endl;
 
 
 
    start = clock();
 
    cout << "divideAndConquer : " << divideAndConquer(0, N - 1) << " elapse time : ";
 
    end = clock();
    time = double(end - start) / CLOCKS_PER_SEC;
    cout << time << endl;
 
 
 
    start = clock();
 
    cout << "dynamicProgramming : " << dynamicProgramming() << " elapse time : ";
 
    end = clock();
    time = double(end - start) / CLOCKS_PER_SEC;
    cout << time << endl;
 
 
    system("pause");
    return 0;
}
 
 

bruteForce : 1646 elapse time : 11.554

divideAndConquer : 1646 elapse time : 0.041

dynamicProgramming : 1646 elapse time : 0.004