문제

문제 링크

어떻게 접근할 것인가

  • 이 문제는 디피로 풀 수 있는 문제이다.
  • 연속된 숫자의 누적합을 미리 구하고 처음부터 하나씩 최소값을 찾고 현재 위치와 비교해가며 n번만에 비교를 마무리한다!

코드

#include <cstdio>

int main(){
    int arr[100001], n, ans = -987654321;
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        scanf("%d", &arr[i]);
    }
    int m = 0;
    if(arr[0] > ans) ans = arr[0]; 
    for(int i = 1; i < n; i++){
        arr[i] += arr[i-1];
        if(arr[i] - arr[m] > ans)ans = arr[i] - arr[m];
        if(arr[i] > ans)ans = arr[i];
        if(arr[m] > arr[i])m = i;
    }
    
    printf("%d", ans);
}

느낀점

  • 시간초과를 해결하는 방법을 찾는데 오래걸렸다.
  • 그래도 내가 스스로 접근법을 떠올린 것에 만족한다!