BOJ 1912번: 연속합

문제 설명

연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하기

🔗 문제 링크

핵심 아이디어

• i 번째 수를 포함하는 최대 연속합을 배열로 두기
• 경우의 수 구하기
  • 이전까지의 연속합에 현재 수를 이어붙이는 경우
  • 이전 거를 다 버리고 새로 시작하는 경우

코드

#include <bits/stdc++.h>
using namespace std;
int n;
int arr[100005];
int d[100005];

int main (){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n;
    for(int i = 0; i < n; i++) cin >> arr[i];
    
    d[0] = arr[0];
    for(int i = 1; i < n; i++){
        d[i] = max(d[i-1] + arr[i], arr[i]);
    }
    cout << *max_element(d,d+n);
}

놓친 부분

• "i 번째 수를 포함하는 최대 연속합을 배열로 두기"

추가사항

• Kadane's Algorithm이라고 불린다고도 함