백준 1912 연속합 c++

문제 출처 : www.acmicpc.net/problem/1912

1912번: 연속합

문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

알고리즘 분류

• 다이나믹 프로그래밍

풀이

어제부터 하루종일 풀어서 예제는 통과했지만, 계속 틀려서 결국 풀이를 본 문제..

부분합이 아닌 연속합이라는 점을 잘 생각하면 쉽게 풀 수 있는 문제다.

 

int arr[10]= {10, -4, 3, 1, 5, 6, -35, 12, 21, -1};

의 케이스에서

dp[0] = 10; 

dp[1] = 6 (10-4 > -4) 

dp[2] = 9 (6+3 > 3)

dp[3] = 10 (9+1 > 1)

dp[4] = 15 (10+5 > 5)

dp[5] = 21 (15+6 > 6) 

dp[6] = -14 (21-35 > -35)   

dp[7] = 12 (-14 +12 < 12) dp[i-1]+arr[i]보다 arr[i]가 더 크기 때문에 앞 부분을 버리고 dp[7]에 arr[7]을 넣어준다.

dp[8] = 33 (12+21 > 21)

dp[9] = 33 (33-1 > -1)

 

이 중에서 최댓값을 고르면 된다.

dp의 값에는 항상 최댓값이 들어와야 한다는 강박에 문제를 푸는 데에 더 어려움을 겪었다.

(ex: dp[2] = 10, dp[6] =21 )

  

코드

#include<iostream>
#include<algorithm>
using namespace std;
int dp[100001];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;
    int *arr = new int[n];
    int mcount = 0;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        if (arr[i] < 0)
            mcount++;
    }
    int ans = -1000;
    for (int i = 0; i < n; i++) {
        dp[i + 1] = max(dp[i] + arr[i], arr[i]);
        ans = max(dp[i + 1], ans);
    }
    cout << ans;



    delete[] arr;


    return 0;
}