[백준 4097] 수익 (C++)

https://www.acmicpc.net/problem/4097

문제

---

연종이는 창업했다. 오늘은 창업한지 N일이 되었고, 매일 매일 수익을 적어놓았다.

어느 날 연종이는 가장 많이 돈을 번 구간이 언제인지 궁금해졌다.

오늘이 창업한지 6일 되었고, 수익이 다음과 같다고 하자.

• 1일: -3
• 2일: 4
• 3일: 9
• 4일: -2
• 5일: -5
• 6일: 8

이때, 가장 많은 돈을 번 구간은 2~6까지이고 총 수입은 14이다.

입력

---

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 N이 주어져 있다. (1 ≤ N ≤ 250,000) 둘째 줄부터 N개의 줄에는 매일 매일의 수익 P가 주어진다. (-10,000 ≤ P ≤ 10,000) 수익은 첫 날부터 순서대로 주어진다. 입력의 마지막 줄에는 0이 주어진다.

 

출력

---

각 테스트 케이스에 대해서 가장 많은 수익을 올린 구간의 수익을 출력한다. 단, 구간이 비어있으면 안 된다.

 

문제 풀이

---

dp 문제.

 

하나의 연속된 구간의 수익의 최댓값을 구하는 문제이다. i 일을 구간에 포함하기로 했다면, 이전의 구간(최댓값을 가지는 임의의 날짜부터 i-1일까지의 구간)을 구간에 포함해야 하는지 확인한다. 만약 이전의 구간이 0보다 작다면 그냥 i번째 일만 선택하는 것이 이득이다. 아니라면 이전의 구간을 포함하는 것이 이득이다.

 

아래는 코드.

#include <iostream>
using namespace std;

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	while (true)
	{
		int N;
		cin >> N;
		if (N == 0)
		{
			break;
		}
		int* arr = new int[N];
		long long* dp = new long long[N];
		long long answer = -2500000001;
		for (int i = 0; i < N; i++)
		{
			cin >> arr[i];
			dp[i] = arr[i];
		}
		for (int i = 1; i < N; i++)
		{
			if (dp[i - 1] >= 0)
			{
				dp[i] += dp[i - 1];
			}
			answer = max(answer, dp[i]);
		}
		std::cout << answer << "\n";
	}
	return 0;
}