[백준 1912] 연속합 (C#, C++) - soo:bak

문제 링크

1912번 - 연속합

설명

수열에서 연속된 구간을 선택하여 그 합이 최대가 되도록 할 때, 그 최댓값을 구하는 문제입니다.

접근법

각 위치에서 그 위치를 끝으로 하는 연속 부분합의 최댓값을 계산합니다. 현재 원소만 선택하는 것과 이전까지의 최대 연속합에 현재 원소를 더하는 것 중 큰 값을 선택합니다.

이전까지의 연속합이 음수라면 새로 시작하는 것이 유리하고, 양수라면 이어가는 것이 유리합니다. 이 과정을 진행하면서 전체 최댓값을 갱신합니다.

모든 수가 음수일 수 있으므로 초기값을 첫 원소로 설정합니다.

---

Code

C#

using System;

class Program {
  static void Main() {
    var n = int.Parse(Console.ReadLine()!);
    var parts = Console.ReadLine()!.Split();
    var v = new int[n];
    for (var i = 0; i < n; i++) v[i] = int.Parse(parts[i]);

    var best = v[0];
    var cur = v[0];
    for (var i = 1; i < n; i++) {
      cur = Math.Max(v[i], cur + v[i]);
      if (cur > best) best = cur;
    }
    Console.WriteLine(best);
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; cin >> n;
  vi v(n);
  for (int i = 0; i < n; i++) cin >> v[i];

  int best = v[0], cur = v[0];
  for (int i = 1; i < n; i++) {
    cur = max(v[i], cur + v[i]);
    best = max(best, cur);
  }

  cout << best << "\n";

  return 0;
}