썸네일 출처: https://ye-yo.github.io/thumbnail-maker/
📖 문제
💡 아이디어
1. 동적 계획법으로 모든 경우의 수 탐색하기..?
총 n개의 수가 주어지면 그 숫자들 중 연속된 몇 개의 수를 고르는 경우의 수는 고른 수의 길이가 1일때, 2일때, ..., n일때로 나눠서 생각할 수 있다.
그리고 길이가 L일때 i번째 수부터 길이만큼의 수를 더한 값을 [i, L]이라고 표현하면,
[i, L] = [i, L-1] + [i+L-1, 1]
이다.
이걸 이용해서 행과 열이 각각 L, i인 매트릭스에 동적계획법으로 모든 경우의 수를 계산한 후, 그 중 최댓값을 찾는 방식을 생각했다.
무식하게 계산하면 길이가 L일때 덧셈을 L-1회 해야 하는 것을 모든 계산을 두 수의 덧셈으로 처리하기 때문에 분명 좀 더 효율적인 방법은 분명하다. 그러나...
n의 최댓값이 100,000이기 때문에 채워야 하는 매트릭스의 크기는 100,000,000,000칸이고 이건 100,000,000,000번에 근접한 횟수만큼 덧셈을 해야 한다는 뜻이다. 아니나 다를까, 이 방식으로 짠 코드는 시간초과에 걸렸다.
2. 인접한 음수와 양수를 합치기
만약 어떤 양수와 인접한 수들이 모두 양수라면 무조건 합하는 것이 더 최댓값에 가깝다. 그리고 만약 인접한 수가 음수임에도 그 뒤에 나오는 양수들의 합이 음수들의 합보다 더 크다면 모두 합하는 것이 더 이득이다. 이 경우에도 연속된 양수들 사이의 연속된 음수들은 모두 더해져야 하므로 미리 더해놓는 것이 연산예 유리하다.
그래서 입력받은 n개의 수를 하나씩 확인하며 이전 수들과 연속된 수라면 이전 수의 합에 더하고, 다른 부호의 수가 나오면 이전까지 더한 합을 벡터에 추가하는 식으로 인접한 음수와 양수를 합친 벡터를 만들었다.
3. 벡터에 저장된 양수를 부분합으로 만들기
벡터에 저장된 뒤에서 두 번째 양수부터 시작한다. 만약 자신 이후의 음수와 양수의 합이 양수가 된다면 둘의 합을 자신에게 더한다. 만약 음수라면 그냥 무시한다. 그 뒤, 자신의 인덱스에 -2를 더한 인덱스, 즉 다음 양수가 있는 인덱스로 이동한다. 그리고 앞의 과정을 반복한다. 이렇게 하면 자신의 바로 뒤 양수가 항상 그 뒤의 연속된 수를 더해서 만들 수 있는 최고의 값이 된다.
매번 값을 계산할 때 마다 최고값을 갱신한다.
이 방식은 n개의 수열에 양수와 음수가 한 번씩 번갈아가며 있다는 가정 하에 n/2번, 즉, 최대 50,000회만에 계산이 끝난다. 앞서 생각한 방법보다 훨씬 빠르다는걸 알 수 있다.
4. 모든 수가 음수인 경우
모든 수가 음수일 수도 있다. 이 경우에는 어떤 두 수를 더해도 무조건 더 손해이므로 가장 큰 단일값이 최댓값이 된다.
⏱️ 최적화
인접한 음수와 양수를 합친 벡터에서 마지막 수가 음수일 경우는 벡터에 포함시키지 않아도 된다. 어떠한 경우에도 그 수는 포함시켰을 때 손해이기 때문이다. 그러므로 벡터의 마지막 수는 항상 양수가 되도록 할 수 있고, 이렇게 하면 벡터를 탐색할 때 마지막 수가 음수인지 양수인지 확인하는 코드를 쓰지 않아도 된다.
마찬가지로 맨 첫번째 수도 음수일 경우 제거해도 되지만, 마지막 수는 음수이던 아니던 로직에 변화가 없기 때문에 그냥 두었다.
✏️ 코드
use std::cmp::{max, min};
use std::io::{stdin, Read, Write, stdout, BufWriter};
const N_MAX: usize = 100_000;
fn main() {
let mut input = String::new();
stdin().read_to_string(&mut input).unwrap();
let mut input = input.split_ascii_whitespace().flat_map(str::parse::<i32>);
let n = input.next().unwrap() as usize;
let mut nums = [0; N_MAX+1];
let mut buffer: Vec<i32> = Vec::new();
let mut maximum = i32::MIN;
let mut has_positive = false;
for i in 0..n {
nums[i] = input.next().unwrap();
if nums[i] > maximum {
maximum = nums[i];
if !has_positive && nums[i] > 0 {
has_positive = true;
}
}
}
if !has_positive {
println!("{maximum}");
return;
}
let mut taking_positive = nums[0] > 0;
let mut partial_sum = 0;
for num in nums.iter().take(n) {
if taking_positive == (*num > 0) {
partial_sum += num;
} else {
taking_positive = *num > 0;
buffer.push(partial_sum);
partial_sum = *num;
}
}
if partial_sum > 0 {
buffer.push(partial_sum);
}
let mut prev_positive = *buffer.last().unwrap();
maximum = max(prev_positive, maximum);
let mut i = (buffer.len() - 3) as i32;
while i >= 0 {
if buffer[(i+1) as usize] + prev_positive > 0 {
buffer[i as usize] += buffer[(i+1) as usize] + prev_positive;
}
maximum = max(maximum, buffer[i as usize]);
prev_positive = buffer[i as usize];
i -= 2;
}
println!("{maximum}");
}
