c++ 연속된 부분 구간 중 그 합이 최대인 구간 찾기

책에 나와 있는 알고리즘이 흥미로워 main 함수까지 작성해봤습니다.

/*

연속된 부분 구간 중 그 합이 최대인 구간 찾기

*/

#include <iostream>

#include <cstdlib>

#include <ctime>

#include <vector>

#include <algorithm>

#include <chrono>

using namespace std;

 

const int MIN = numeric_limits<int>::min();

//A[]의 연속된 부분 구간의 최대 합을 구한다 시간복잡도 O(N^3)

int inefficientMaxSum(const vector<int> &A)

{

        int N = A.size(), ret = MIN;

        for (int i = 0; i < N; i++)

               for (int j = i; j < N; j++)

               {

                       //구간 A[i...j]의 합을 구한다

                       int sum = 0;

                       for (int k = i; k <= j; k++)

                              sum += A[k];

                       ret = max(ret, sum);

               }

        return ret;

}

 

//A[]의 연속된 부분 구간의 최대 합을 구한다 시간 복잡도 O(N^2)

int betterMaxSum(const vector<int> &A)

{

        int N = A.size(), ret = MIN;

        for (int i = 0; i < N; i++)

        {

               int sum = 0;

               for (int j = i; j < N; j++)

               {

                       //구간 A[i...j]의 합을 구한다

                       sum += A[j];

                       ret = max(ret, sum);

               }

        }

        return ret;

}

 

//A[lo...hi]의 연속된 부분 구간 최대 합을 구한다 시간 복잡도 O(nlogn)

int fastMaxSum(const vector<int> &A, int lo, int hi)

{

        //기저 사례:구간의 길이가 1일 경우

        if (lo == hi)

               return A[lo];

        //배열을 A[lo..mid], A[mid+1..hi] 두 조각으로 나눈다

        int mid = (lo + hi) / 2;

        //두 부분에 모두 걸쳐 있는 최대 합 구간을 찾는다 이 구간은

        //A[i..mid]와 A[mid+1,,j] 형태를 갖는 구간의 합으로 이루어진다

        //A[i..mid] 형태를 갖는 최대 구간을 찾는다

        int left = MIN, right = MIN, sum = 0;

        for (int i = mid; i >= lo; i--)

        {

               sum += A[i];

               left = max(left, sum);

        }

        //A[mid+1..j] 형태를 갖는 최대 구간을 찾는다

        sum = 0;

        for (int j = mid + 1; j <= hi; j++)

        {

               sum += A[j];

               right = max(right, sum);

        }

        //최대 구간이 두 조각 중 하나에만 속해 있는 경우의 답을 재귀호출로 찾는다

        int single = max(fastMaxSum(A, lo, mid), fastMaxSum(A, mid + 1, hi));

 

        //두 경우 중 최대치를 반환한다

        return max(left + right, single);

}

 

//A[]의 연속된 부분 구간의 최대 합을 구한다 시간 복잡도 O(n)

int fastestMaxSum(const vector<int> &A)

{

        int N = A.size(), ret = MIN, psum = 0;

        for (int i = 0; i < N; i++)

        {

               psum = max(psum, 0) + A[i];

               ret = max(psum, ret);

        }

        return ret;

}

 

int main(void)

{

        using namespace std::chrono;

 

        vector<int> v;

        high_resolution_clock::time_point t1, t2;

        duration<double> time_span; //시간 재기 위해

        srand((unsigned)time(NULL));

       

        for (int i = 0; i < 100; i++)

               v.push_back(rand() % 1000);

       

        cout << "v: ";

        for (vector<int>::size_type i = 0; i < v.size(); i++)

               cout << v[i] << " ";

        cout << endl << endl;

 

        t1 = high_resolution_clock::now();

        cout << "부분 구간의 최대 합: " << inefficientMaxSum(v) << endl;

        t2 = high_resolution_clock::now();

        time_span = duration_cast<duration<double>>(t2 - t1);

        cout << "inefficientMaxSum: " << time_span.count() << "초" << endl << endl;

 

        t1 = high_resolution_clock::now();

        cout << "부분 구간의 최대 합: " << betterMaxSum(v) << endl;

        t2 = high_resolution_clock::now();

        time_span = duration_cast<duration<double>>(t2 - t1);

        cout << "betterMaxSum: " << time_span.count() << "초" << endl << endl;

 

        t1 = high_resolution_clock::now();

        cout << "부분 구간의 최대 합: " << fastMaxSum(v, 0, v.size()-1) << endl;

        t2 = high_resolution_clock::now();

        time_span = duration_cast<duration<double>>(t2 - t1);

        cout << "fastMaxSum: " << time_span.count() << "초" << endl << endl;

 

        t1 = high_resolution_clock::now();

        cout << "부분 구간의 최대 합: " << fastestMaxSum(v) << endl;

        t2 = high_resolution_clock::now();

        time_span = duration_cast<duration<double>>(t2 - t1);

        cout << "fastestMaxSum: " << time_span.count() << "초" << endl << endl;

 

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

참고: [프로그래밍 대회에서 배우는 알고리즘 문제해결전략]