[백준] 1912 연속합 c++

 

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

KEY

• i-1번째까지의 수열의 합에 i번째 숫자를 더해도 i번째 숫자보다 작다면 차라리 i번째 숫자부터 다시 세는 것이 낫다.

 

수열 {10, -4, -9, 8}로 예를 들어보자.

• 처음은 10이다. 최댓값은 10 그대로일 것이다.
• 두번째 -4로 왔다. 최댓값은 (10-4)와 -4 둘 중에 큰 6이 된다.
• 세번째 -9로 왔다. 최댓값은 (6-9)와 -9 둘 중에 큰 -3이 된다.
• 마지막 8이다. 최댓값은 (-3+8)와 8 둘 중에 큰 8이 된다.
• 이렇게 완성된 최댓값을 저장한 배열은 {10, 6, -3, 8}이고, 정답은 이 중 최댓값인 10이다.

 

Code

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
#include<string>
using namespace std;
const int MAX = 100001;
int n;
int arr[MAX];
int dp[MAX];
int answer = -1000 * 100001;
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
 
    dp[0] = arr[0];
    for (int i = 1; i < n; i++) {
        dp[i] = max(dp[i - 1] + arr[i], arr[i]);
        
    }
 
    //최댓값 출력
    for (int i = 0; i < n; i++) {
        answer = max(answer, dp[i]);
    }
    cout << answer;
}