Solution#
Memo#
- dp문제
- 생각이 꼬이면 빅트롤을 한다.
- 주석의 풀이가 틀렸지만 이상한짓을 한 코드
- 기본적으로 수열, dp, psum을 생각하며 조급하게 굴다가 의미없는짓을 세번이나 했다.
- 복기하면
- psum을 구할 필요가 없었다.
- 구간합중 가장 큰 수열값으로 브루트포스 풀이를 했다.
- 직전 구간합과 지금 구하고자 하는 값과의 연관관계에 집중을 전혀 하지 못했다.
// Baekjoon - 1912
// https://www.acmicpc.net/problem/1912
use std::cmp::max;
use std::io::{self, Read, Write};
fn main() {
let mut stdin = io::stdin().lock();
let mut stdout = io::stdout().lock();
let mut input = String::new();
stdin.read_to_string(&mut input).unwrap();
let mut lines = input.lines();
let _n: usize = lines.next().unwrap().parse().unwrap();
let mut inputs: Vec<i32> = lines.next().unwrap()
.split_whitespace()
.map(|x| x.parse().unwrap())
.collect();
// 지금까지 발견된 최대 부분합
let mut max_so_far = inputs[0];
// 현재 위치에서 끝나는 최대 부분합
let mut max_ending_here = inputs[0];
for i in 1..inputs.len() {
max_ending_here = max(inputs[i], max_ending_here + inputs[i]);
max_so_far = max(max_so_far, max_ending_here);
}
write!(stdout, "{}", max_so_far).unwrap();
}
// fn main() {
// let mut stdin = io::stdin().lock();
// let mut stdout = io::stdout().lock();
// let mut input = String::new();
// stdin.read_to_string(&mut input).unwrap();
// let mut lines = input.lines();
//
// let n: usize = lines.next().unwrap().parse().unwrap();
// let mut inputs: Vec<i32> = lines.next().unwrap()
// .split_whitespace()
// .map(|x| x.parse().unwrap())
// .collect();
//
// let mut p_sum = vec![0; inputs.len()];
// let mut dp = vec![0; inputs.len()];
//
// p_sum[0] = inputs[0];
// dp[0] = inputs[0];
//
// for i in 1..inputs.len() {
// p_sum[i] = p_sum[i - 1] + inputs[i];
// }
//
// for i in 1..inputs.len() {
// let mut tmp_max = p_sum[i];
// for j in 0..i {
// tmp_max = max(p_sum[i] - p_sum[j], tmp_max)
// }
// dp[i] = tmp_max;
// }
//
// let output = dp.iter().max().unwrap();
// write!(stdout, "{}", output).unwrap();
// }