[1912] 연속합

이문제는 정답률이 27퍼센트라서 어려울것같았는데 의외로 두번만에 풀었다.

첫번째는 res변수를 0으로 초기화해서 최댓값을 구할때 음수가 나오면 처리가 안돼서 틀렸다.

#include <cstdio>
#include <algorithm>
using namespace std;
​
int main(){
    int N = 0;
    int a[100001];
    int d[100001];
    scanf("%d",&N);
​
    int res = -10001;
    for(int i = 0;i<N;i++){
        scanf("%d",&a[i]);
        d[i] = max(a[i],d[i-1]+a[i]);
        if(d[i] > res){
            res = d[i];
        }
    }
    printf("%d\n",res);
}

경우는 두가지이다.

1. 현재 숫자가 저번 숫자에 연속해서 더해지는 수 — d[i] = d[i-1]+[ai]

2. 현재 숫자가 첫번째로 선택된 수 — d[i] = a[i]

둘중 최댓값을 넣으면 된다.

그 후 d[i]중 최댓값을 찾으면 연속합중 최댓값을 찾을 수 있다.