백준 1912번 연속합

문제 링크입니다: https://www.acmicpc.net/problem/1912

우선 완전탐색법으로 작성한 다음 동적계획법으로 프로그램을 작성했습니다.

algospot에서 배운대로 재귀를 사용하려고 했지만 적당한 기저사례를 찾기 힘들어 반복문으로 작성했습니다.

/*

n개의 정수로 이루어진 임의의 수열이 주어진다.

우리는 이 중 연속된 몇 개의 숫자를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다.

단, 숫자는 한 개 이상 선택해야 한다.

*/

#include <iostream>

#include <algorithm>

using namespace std;

 

int cache[100000]; //최대 100000

int arr[100000];

int length;

 

//Brute Force(완전 탐색) 기법(시간초과)

/*

int maxSum(int start, int next)

{

        int sum = 0;

        for (int i = start; i < next; i++)

               sum += arr[i];

        return sum;

}

 

int main(void)

{

        cin >> length;

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

               cin >> arr[i];

        int maximum = arr[0];

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

               for (int j = i + 1; j < length; j++)

                       if (maximum < maxSum(i, j))

                              maximum = maxSum(i, j);

        cout << maximum << endl;

        return 0;

}

*/

 

void initialize(void) //cache 초기화

{

        cache[0] = arr[0];

        for (int i = 1; i < length; i++)

        {

               cache[i] = arr[i];

               if (cache[i] < cache[i - 1] + arr[i])

                       cache[i] = cache[i - 1] + arr[i];

        }

}

 

//동적계획법 사용

int maxSum(void)

{

        initialize();

        int result = cache[0];

        for (int i = 1; i < length; i++)

               if (result < cache[i])

                       result = cache[i];

        return result;

}

 

int main(void)

{

        cin >> length;

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

               cin >> arr[i];

       

        cout << maxSum() << endl;

        return 0;

}

 

개발환경:Visual Studio 2017

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