1912_연속합

Concept & Idea

연속합이라고해서 투포인터 개념을 이용해 문제를 해결하려 했는데, 그냥 간단한 이중 포문으로 해결하였다.
처음엔 아무 조건없이 이중포문으로만 해결하니, 시간초과를 마주하였는데 간단한 res<dp[i] 조건을 통해 해결할 수 있었다.
이전에 기록된 DP[j-1]배열의 누적 합과 현재 자기 자신을 더한 값, DP[j]를 비교하여 문제를 해결 할 수 있었다.
여태 풀었던 DP문제들은 입력되는 수가 양수만 들어와서, 입력으로 음수가 들어오는 이 문제를 DP배열을 입력으로 초기화해놓음으로 해결 할 수 있었다.

5 -1 -1 -1 -1 -1

위와 같은 예시를 통해, 예외를 알아낼 수 있었다.

Code

#include <iostream>
using namespace std;
int n;
int map[100001];
int dp[100001];
int res=-1001;
int main() {
    cin>>n;
    for(int i=1; i<=n; i++) {
        cin>>map[i];
        dp[i]=map[i];
    }
    for(int i=1; i<=n; i++) {
        if(res<dp[i]) {
            for(int j=i; j<=n; j++) {
                if(dp[j]<dp[j-1]+map[j])
                    dp[j]=dp[j-1]+map[j];
                if(res<dp[j])
                    res=dp[j];
            }
        }
    }
    cout<<res<<endl;
}

 

Fealing

검사할 필요 없는 요소를 체크하여 시간을 줄여나가야 하는 것이 중요한 것 같다.
또한 입력받는 수의 범위가 음수도 가능하기에, 한번 더 생각해보아야 하는 문제였다.