합이 0에 가장 가까운 구간의 합

부분합을 이용하여 합이 0에 가장 가까운 구간의 합을 구하는 프로그램입니다.

/*

합이 0에 가장 가까운 구간의 값 구하기

*/

#include <iostream>

#include <vector>

#include <algorithm>

#include <map>

using namespace std;

 

const int MAX = 987654321;

 

int compare(const void *num1,const void *num2) //ascending

{

        return (*(int*)num1 - *(int*)num2);

}

 

int rangeValue(const vector<int> &v)

{

        int psum[50];

        psum[0] = v[0];

        //부분합 구하고

        for (int i = 1; i < v.size(); i++)

               psum[i] = psum[i - 1] + v[i];

        //부분합 정렬

        qsort(psum, v.size(), sizeof(int), compare);

 

        int result = MAX;

        //0에 가깝다는 말은 psum[]의 두 값의 차이가 가장 적다는 뜻

        for (int i = 1; i < v.size(); i++)

               result = min(psum[i] - psum[i - 1], result);

        return result;

}

 

void initialize(vector<int> &v)

{

        v.push_back(-14);

        v.push_back(7);

        v.push_back(2);

        v.push_back(3);

        v.push_back(-8);

        v.push_back(4);

        v.push_back(-6);

        v.push_back(8);

        v.push_back(9);

        v.push_back(11);

}

 

int main(void)

{

        vector<int> v;

        initialize(v);

        cout << "0에 제일 근접한 부분합: " << rangeValue(v) << endl;

        return 0;

}

개발환경:Visual Studio 2017

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

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