백준 1912번 - 연속합

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

문제의 조건을 보면 n의 크기가 100000이다. 
시간 복잡도를 계산해보면 O(N^2)가 될 경우 시간초과가 나기 때문에 dp로 접근해야 한다.


문제를 보면서 2가지 방법을 생각했다.
첫 번째는 흔히 우리가 알고 있는 dp점화식을 세운 뒤에 푸는 방법,
두 번째는 수학적으로 계산하는 방식이다.


첫 번째 방법은 dp[n]을 n까지를 고려 했을 때 연속합이다.

즉 dp[n]은 n번째를 포함할 때는 dp[n-1]과 n번째의 값을 더한 값이 될 것이고, n번째까지 연속해서 더하지 않을 경우에 

dp[n]은 n번째의 값인 arr[i]이다. 그리고 반복문을 돌 때마다 출력해야할 ans값의 최대값을 계산해 주면 된다.

두 번째 방법은 첫 번째 방법과 유사하지만 sum이라는 변수를 이용했다.
문제를 접근할 때 n번째를 더해줄지 말지를 계산하는 식으로 했다. n번째의 dp값을 계산하는 것이 아닌, 

sum이라는 변수를 통해서 n번째까지 더해줄 경우에 sum의 값에 n번째 값을 더해주고 

만약에 포함하지 않을 경우에는 n번째부터 시작하는 것으로 계산하였다.

 

이 경우에 만약 n번째를 포함하여 연속합을 구한 경우에도 0보다 작고 n번째 값 자체도 0보다 작을 경우에는

 sum의 값을 0으로 설정하여 n+1번째부터 계산할 수 있도록 하였다.

만약 이대로 제출 한다면 하나의 반례때문에 오류가 날것이다. 바로 모든 값이 음수인 경우이다. 

sum의 값을 0으로 하게 되면 최대값이 0 이 나올텐데, 실제로는 음수 값 중에서 가장 큰 값을 출력해야 한다. 

그렇기 때문에 맨 처음에 양수인 값의 개수를 구한 다음에 모두 음수인 경우, 음수 중에서 최대값을 구해서 그 값을 출력하면 된다.


#1

#include <iostream>
#include <algorithm>
using namespace std;
 
int main(){
    
    int n,ans=0;
    cin>>n;
    
    int arr[100001]={0};
    int dp[100001]={0};
 
    for(int i=1;i<=n;i++)
        scanf("%d",&arr[i]);
    
    ans=dp[1]=arr[1];
    for(int i=2;i<=n;i++){
        dp[i]=max(arr[i],dp[i-1]+arr[i]);
        ans=max(ans,dp[i]);
    }
    
    cout<<ans<<endl;
    return 0;
}

#2

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main(){
    int n,ans=-1000,sum;
    cin>>n;
    
    int cnt=0; //양수 개수
    vector<int> vec(n,0);
    for(int i=0;i<n;i++){
        scanf("%d",&vec[i]);
        
        if(vec[i]>=0)
            cnt++;
        
        ans=max(ans,vec[i]);
    }
    
    if(cnt==0){
        cout<<ans<<endl;
        return 0;
    }
    
    ans=sum=vec[0];
    for(int i=1;i<n;i++){
        
        if(sum+vec[i]>=0)
            sum+=vec[i];
        else
            sum=max(0,vec[i]); //i번째 포함 유무
        
        ans=max(ans,sum);
    }
    
    cout<<ans<<endl;
    
    return 0;
}