[ 백준 1912 ] 연속합 (C++)

백준의 연속합(1912) 문제이다.

( 문제 바로가기 )

( 문제를 다시 푸는 과정에서 , 보다 구체적인 설명을 다시 포스팅 해 놓았습니다.

  아래의 글을 읽으셔도 무관하지만 , 더 구체적인 설명을 원하시는 분들께서는 아래의 링크를 타고 오시면

  더욱 구체적인 설명을 보실 수 있습니다.

  [ 백준 연속합(1912) ] )

[ 문제설명 ]

- 수열의 크기와, 그 크기만큼의 값들이 입력으로 주어진다.

- 주어진 수열에서 연속된 숫자들의 합들 중에서 가장 최댓값을 구한다.

[ 문제풀이 ]

1) 최댓값을 저장하는 DP라는 배열과, 입력으로 주어지는 숫자들을 저장할 Arr배열 2개를 사용한다.

2) DP[N] = ' N번째 숫자까지의 최댓값' 을 의미한다.

3) 중간중간 음의정수들도 포함되어 있으므로, 숫자 하나하나씩 더해가면서 최댓값을 갱신시켜주면 된다.

4) 주어질 수 있는 값의 최대범위는 1000이고, 수열의 크기의 최대범위는 100000이기 때문에 최댓값을 계산해보면

   int형의 범위를 벗어나므로 long long 자료형을 사용해 줘야 통과할 수 있다.

5) 초기 식을 구해보면 DP[0] = Arr[0]가 된다.

   5-1) 당연히 0번째 까지의 최댓값은 수열 중 0번째 값이므로

   5-2) DP[1]의 경우는, DP[0] + Arr[1] vs Arr[1] 둘 중 최댓값이 된다.

         - 왜냐하면, 예를 들어 Arr[0] = -5, Arr[1] = 10 이라고 해보자. DP[0]는 초기식에 의해 -5가 될 것이고

           DP[1]의 최댓값은 Arr[1]하나만 선택하는 10이 될것이다. (-5 + 10 < 10) 이기 때문에

6) 5-2)의 말로 점화식을 도출해보면 DP[i] = Max(DP[i-1] + Arr[i], Arr[i])가 된다.

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
#define MAX 100000+1
typedef long long ll;
 
using namespace std;
 
int N;
ll Arr[MAX];
ll DP[MAX];
ll Answer;
 
ll Bigger(ll A, ll B) { if (A > B) return A; return B; }
 
void Input()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> Arr[i];
    }
}
 
void Solution()
{
    DP[0] = Arr[0];
    Answer = DP[0];
    for (int i = 1; i < N; i++)
    {
        DP[i] = Bigger(DP[i - 1] + Arr[i], Arr[i]);
        Answer = Bigger(Answer, DP[i]);
    }
}
 
void Solve()
{
    Input();
    Solution();
 
    cout << Answer << endl;
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}