[알고리즘] 1912 : 연속합

문제 풀러 바로가기 :: 1912 연속합

💡 문제

n개의 정수로 이루어진 임의의 수열이 주어진다.
우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 $10, -4, 3, 1, 5, 6, -35, 12, 21, -1$ 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

💻 입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고
둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다.
수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

💻 출력

첫째 줄에 답을 출력한다.

🤔 내가 생각한 로직이라고 쓰고 삽질이라 읽는다

이건 다이나믹 프로그래밍(DP)로 풀 수 있는 문제 같았다.
처음에 DP의 설계과정 중 dp 테이블 정의를 다음과 같이 했다.

• dp[i]
  = i번째 요소를 포함하여 가장 큰 연속합

근데 이렇게 정의하다보니까 테이블 정의 범위가 너무 모호하다는 생각을 했다.
그래서 dp테이블은 좀 더, 가장 크다는 그 연속합을 어떻게 구할 것이냐?를 담고 있어야 한다고 생각했다.
만약 dp[i-1]가 음수라면, a[i]자체만으로도 가장 큰 연속합이 될 수 있다. 아니면 , dp[i]는 항상 dp[i-1]+a[i]이다.

• dp[i]
  = max(a[i], dp[i-1]+a[i])

이제 초기값을 셋팅해보자.
dp[0] 은 0번째 인덱스를 가리키는 시점에서 가장 큰 연속합이니까 당연히 a[0]의 값과 같을 것이고, dp[1]부터는 위의 점화식을 그대로 따라가면 된다.

💻 정답 코드

#include <iostream>
using namespace std;
int n;
int a[100004], dp[100004];
int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  cin >> n;
  for(int i = 0; i < n; i++) {
    cin >> a[i];
  }
  dp[0] = a[0];
  int max_val=-987654321;
  for(int i = 1; i < n; i++) {
    dp[i]= max(a[i], dp[i-1]+a[i]);
  }
  for(int i = 0; i < n; i++) {
    max_val = max(dp[i], max_val);
  }
  cout << max_val <<"\n";
  return 0;
}