[백준/Rust] 1912번 : 연속합

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

---

문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

입력

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

출력

첫째 줄에 답을 출력한다.

예제 입출력

---

풀이

수열을 순회하면서 이전까지의 최대합을 기록해두고 이를 통해 이번 위치에서 최대값을 구하는 것이다. O(N)의 시간 복잡도로 해결이 가능하다.

---

코드

use std::io; // 입출력 모듈

fn calc(n: usize, s: Vec<i32>) -> i32 { // 함수 정의 n->배열 길이, s->배열
    // dp 변수 선언(let), 변수 변경 예약어(mut)
    // 벡터로 선언해 배열 생성
    // 길이가 n, 값은 0으로 초기화
    let mut dp = vec![0; n];
    // dp 벡터의 첫 번째 값은 벡터 s의 첫 번째 값으로 설정
    dp[0] = s[0];

    for i in 1..n { // 1부터 n-1까지 반복, 간격 미설정(1)
        // dp[i]를 s[i]와 dp[i-1] + s[i] 중
        dp[i] = s[i].max(dp[i - 1] + s[i]); //큰 값으로 설정
    }
    // dp 벡터에서 최대 값을 반환
    // iter : 이터레이터(요소 순회) 리턴
    // unwrap : Option<&i32> -> '&i32'로 변환
    // * : 실제 값(i32 : 32비트 정수 타입)으로 변환
    *dp.iter().max().unwrap()
}

fn main() {

    let mut input = String::new(); // 입력을 받을 문자열 생성
    io::stdin().read_line(&mut input).unwrap(); // 입력 한 라인 읽고 저장
    let n: usize = input.trim().parse().unwrap(); // 문자열->숫자로 변환, n에 저장
    input.clear(); // 비우기

    io::stdin().read_line(&mut input).unwrap();
    let s: Vec<i32> = input // 벡터 s에 저장
        .trim() // 앞 뒤 공백 제거
        .split_whitespace()// 공백을 기준으로 나눔
        .map(|x| x.parse().unwrap()) // i32로 변환
        .collect(); // 벡터 내부에 취합

    // 함수 호출, 결과 출력
    println!("{}", calc(n, s));
}

---