백준 4097번 수익 - C++ 풀이

---

 

1. dp[i] = i일로 끝나는 구간 중 최고수익 구간의 수익
2. dp[i] = i-1일로 끝나는 최고수익 구간에 i일을 추가하거나 i일로 구간을 새로 시작하는 경우 중 최댓값

 

1. dp[i] = i일로 끝나는 구간 중 최고수익 구간의 수익

 dp[i]를 위와 같이 정의하자. 예를 들어, dp[3]은 1-3일인 구간, 2-3일인 구간, 3-3일인 구간 중 최고 수익인 구간의 수익이다.

 

2. dp[i] = i-1일로 끝나는 최고수익 구간에 i일을 추가하거나 i일로 구간을 새로 시작하는 경우 중 최댓값

 구간은 연속된 일자로 이루어져 있다는 성질을 이용한다. i일로 끝나는 구간은 1. i-1로 끝나는 구간에 i일을 추가하거나, 2. i일로 시작하면서 끝나는 구간(i일로만 이루어진) 둘 중 하나이다. 이 두 구간 중 최댓값을 선택하면 된다.

 

---

#include <iostream>
#include <vector>

using namespace std;

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

    while (1) {
        int N;
        cin >> N;
        if (N == 0) break;
        
        vector<int> profits(N+1, 0);
        for (int i=1; i<=N; i++) cin >> profits[i];
        
        // dp[i]: i일로 끝나는 구간 중 최고수익 구간의 수익
        vector<int> dp(N+1);
        int max_profit = -(1e5+1);
        for (int i=1; i<=N; i++) {
            // (i-1)일로 끝나는 구간에 i일을 더하기 or i일로 구간 새로 시작
            dp[i] = max(dp[i-1] + profits[i], profits[i]);
            max_profit = max(max_profit, dp[i]);
        }
        
        cout << max_profit << "\n";
    }
}