<알고리즘 문제풀이&연습>/[C++] 백준

[백준 1912] 연속합 (수열)

사용자 BlockDMask 2017. 9. 12. 15:15
반응형
  • 안녕하세요. BlockDMask 입니다.

  • 상큼하게 월요일 문제 풀어봤습니다.

0. 문제

  • 백준 1912 연속합

  • BOJ 1912 연속합

1. 문제설명


N개의 수열이 주어집니다.

이중 연속된 몇개의 숫자를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 합니다.

선택할 수는 적어도 하나 이상 이어야합니다. 


N의 범위는 

(1 <= N <= 100000)

이고, 


정수(num)들의 범위는 

(-1000 <= num <= 1000)

입니다.


2. 풀이과정


앞에서부터 더해온 값 중 최대값 vs 새로운 값 

을 비교해서

최대값을 구하는 방식을 생각했습니다.


배열을 2개를 선언 한후

arr 배열에 문제에서 주어진 수열을 집어 넣습니다.

tmpArr 배열에는 arr 배열의 다음값(i)과 이전의 값(i-1) 을 더한것 을 비교해서 큰 값을 집어 넣습니다.


3. 코드


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
32
33
34
35
#include<iostream>
#include<cstdio>
using namespace std;
 
int arr[100001];
long long sumArr[100001];
 
long long max(long long a, long long b){
    if(a>b) return a;
    return b;
}
 
int main(void){
    int n;
    long long tmp;
 
    //입력
    cin >> n;
    for(int i=0; i<n; i++){
        scanf("%d"&arr[i]);
    }
 
    //계산
    sumArr[0= arr[0];
    tmp = arr[0];
    for(int i=1 ;i<n; i++){
        sumArr[i] = max(sumArr[i-1+ arr[i], arr[i]);
        tmp = max(sumArr[i], tmp);
    }
 
    //출력
    cout << tmp;
    return 0;
}
 
cs


4. 인증


문제 출처 - https://www.acmicpc.net/problem/1912

감사합니다. 도움이 되셨다면 하트 한번 눌러주세요!

반응형