백준 1912 C++ (연속합)

LIS와 DP 응용문제였다.

LIS을 외우기만 하면 못 풀고, 이해하고 응용할 줄 아는 사람은 어렵지 않게 풀었을 것이다.

시간 제한	메모리 제한	정답률
1초	128MB	29.909%

문제

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

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

입력

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

출력

첫째 줄에 답을 출력한다.

핵심

LIS를 응용하는 문제이다.
dp[k] : k번째 숫자로 끝나는 부분합들 중 합이 가장 큰 값

코드

#include <iostream>
#include <algorithm>

using namespace std;

int n;
int arr[100010];
int dp[100010]; // dp[k] : k번째 수가 마지막인 부분합들 중 합이 가장 큰 값
int answer;



int main(int argc, char* argv[]) {
	ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n;
    
    for(int i=1;i<=n;i++){
        cin >> arr[i];
    }
    
    dp[1] = arr[1]; // 초항은 당연히 첫번째 숫자 값이다.
    
    for(int i=2;i<=n;i++){
        if(dp[i-1] > 0){ // 이전에 더해놨던 게 양수라서 더하면 이득인 경우
            dp[i] = dp[i-1] + arr[i]; // 전 항에서 계산한 값(dp[i-1])을 더해줌.
        }
        else{ // 이전에 더해놨던게 음수라서 더하면 오히려 손해인 경우
            dp[i] = arr[i]; // 굳이 더하지 않음.
        }
    }
    
    answer = dp[1];
    for(int i=2;i<=n;i++){
        if(answer < dp[i]) answer = dp[i]; // dp[n]이 항상 최댓값은 아니기 때문에, dp의 값들 중 최댓값을 찾아야한다.
    }
    
    cout << answer << '\n';
	
	return 0;
}