백준 No.1912 [연속합]

Baekjoon Online Judge No.1912 [연속합]

---

   Problem   

1912번: 연속합

---

   Code   

#include <iostream>
#include <vector>
 
using namespace std;
 
int N;
vector<int> nums;
 
void input() {
    cin >> ::N;
    nums.assign(N, 0);
 
    for (int i = 0; i < N; i++)
        cin >> nums[i];
}
 
int solve() {
    vector<int> dp(N, 0);
 
    dp[0] = nums[0];
    int ans = dp[0];
 
    for (int i = 1; i < N; i++) {
            dp[i] = max(nums[i], nums[i] + dp[i - 1]);
            ans = max(ans, dp[i]);
    }
 
    return ans;
}
 
int main() {
    input();
    
    int ans = solve();
    cout << ans;
}

---

   How to solve   

  만약 수열의 모든 수가 양수라면 모조리 다 더해버린다면 그 값이 답이 될 것이다. 그 말은 즉, 수열에서 음수에 대해서 만 잘 처리하면 된다는 말이 될 것이다. 그렇다면 이 문제의 점화식을 세우기 위해 고려해볼 사항은 다음과 같다.

 

• case A) dp[ i ] = nums[ i ] + dp[ i - 1 ] 로 계속 더하는게 제일 큰가?
• case B) dp[ i ] = nums[ i ] 로 새로 더해나가는게 제일 큰가?

  그리고 이 사항에 대해선 다음과 같이 정리할 수 있다.

사진을 클릭하면 더 선명하게 보실 수 있습니다 :)

  결국, 이 경우들에 대해선 모두 dp[ i ] = nums[ i ] 아니면 dp[ i ] = nums[ i ] + dp[ i - 1 ] 이 됨을 알 수 있다. 따라서 dp[ i ]의 값은 위 코드 24번째 line 과 같이 max(nums[ i ], nums[ i ] + dp[ i - 1 ]) 가 된다.