(1912) 연속합

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

단계별로 풀어보기

21단계(동적 계획법 1) 5번째

 

 

 

dp[k]을 1부터 k번째까지의 수 중 k번째 수를 선택했으면서 연속된 부분합의 최대라고 하자.

수는 연속해서 선택해야 하므로 dp[k]는 dp[k-1]에 k번째 수를 더한 합, 또는 그냥 k번째 수 중 큰 값이다.

이때 우리가 원하는 답은 dp[n]이 아니라 전체 경우 중 최대값이므로 dp[1]~dp[n] 중 최대값이다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;

int main() 
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, ans;
  
  cin >> n;
  
  vector<int> v(n+1), dp(n+1);
  
  for(int i=1;i<=n;i++)  cin >> v[i];
  
  dp[1]= v[1];  ans= dp[1];
  
  for(int i=2;i<=n;i++){
    dp[i]= max(dp[i-1]+v[i], v[i]);
    ans= max(ans, dp[i]);
  }
  
  cout << ans;
  
  return 0;
}

 

 

 

조금 간단한 설명으로는, 어느 시점까지 부분합을 구했을 때 음수가 나왔다면 여기서 계속 더해 부분합을 구하는 것보다 버리고 이번 원소부터 다시 시작하는 것이 이득이다. 다만 구현 방식에 따라 모든 원소가 음수인 엣지 케이스에 제대로 작동하지 않을 수 있으니 주의해야 한다.

#include <iostream>
#include <vector>
using namespace std;

int main() 
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, s;
  
  cin >> n >> s;
  
  int ans= s;
  
  for(int i=1;i<n;i++){
    int t;
    
    cin >> t;
    
    s= s<0 ? t : s+t;
    ans= max(ans, s);
  }
  
  cout << ans;
  
  return 0;
}