티스토리 뷰

728x90

https://www.acmicpc.net/problem/1912

 

1912번: 연속합

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

www.acmicpc.net

수학 C++

시간복잡도가 문제

O(N)으로 풀어야 하는 문제인 것 같다.

배열을 총 두개를 사용했는데,

처음 입력받은 숫자가 들어있는 배열과 본인을 포함하는 연속된 수들의 합 중 최댓값을 저장하고 있는 배열

바로 전 수를 포함한 최대 연속된 수의 합에 본인을 더한 것과 본인을 비교해서 큰 값을 배열에 저장한다.

그 배열에서 가장 큰 값이 연속된 수의 최대값이 된다.

로직에서 힌트를 조금 얻었다.

 

소스코드

#include <iostream>
#include <cmath>
using namespace std;

int main(){
    int n;
    cin >> n;
    int* nums = new int [n];
    int* maxs = new int [n];
    for(int i = 0 ; i < n ; i++){
        cin >> nums[i];
    }
    maxs[0] = nums[0];
    for(int i = 1 ; i < n ; i++){
        maxs[i] = max(maxs[i-1] + nums[i], nums[i]);
    }
    int max = maxs[0];
    for(int i = 1 ; i < n ; i++){
        if(max < maxs[i])
            max = maxs[i];
    }
    cout << max;
    return 0;
}
728x90
250x250
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함