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

• 안녕하세요. 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. 코드

#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;
}
 

4. 인증

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

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