글 읽기 - 1912 연속합 모르겠습니다....

doordo 6년 전 0

요즘 다시 알고리즘 공부하는 중이라 하루에 몇개씩 문제 풀어보고 있는데

이 문제에서 막혔습니다.

나중에 합하다보면 int 범위를 넘어가나 싶어서 longlong형 으로 바꿔봤는데도 틀렸다고 나오던데

어떻게 풀어가야 할까요?

#include <iostream>
#include <cstdlib>
using namespace std;
int max(int a, int b){
    return a > b ? a : b;
}
int main(void){
    int N, result = 0;
    cin >> N;
    
    int* arr = (int*)malloc(sizeof(int)*N);
    //숫자 넣을 배열
    int* arr2 = (int*)malloc(sizeof(int)*N);
    //연속합 넣을 배열
    
    for (int i = 0; i < N; i++){
        cin >> arr[i];
    }
    
    arr2[0] = arr[0];
    
    for (int i = 1; i < N; i++){
        arr2[i] = max(arr2[i - 1] + arr[i], arr[i]);
    }

    for (int i = 0; i < N; i++){
        result = max(arr2[i], result);
    }
    
    cout << result;
    
    free(arr);
    free(arr2);
    return 0;
}