백준 1912 - 연속합

문제

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

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

코드

const [[n], int] = input;
const dp = Array(n).fill(Infinity);
dp[0] = int[0];
for (let i = 1; i < n; i++) {
  dp[i] = dp[i - 1] + int[i] < int[i] ? int[i] : dp[i - 1] + int[i];
}
console.log(Math.max(...dp));

풀이

dp라길래 되게 엄청 점화식끼리 엄청난 연관성이 있는 그런 문제인 줄 알았으나... 그냥 처음에 dp라는 말 못보고 풀었더라면 더 빨리 풀었을듯
dp[i]를 i번째의 최대 합이라고 설정해봤음
그러면 dp[0] - int[0] (당연히 자기 자신밖에 없으니까)
dp[1] - 1번째에서의 최대 합은 10 + (-4) = 6이 됨
이렇게 가다가... 12에서는 앞의 값을 버리고, 12부터 시작하는게 더 큰 값이 됨(마이너스를 앞에서 만나거나 하면 이렇게 되는듯)
점화식으로 정리하면 dp[i]는 dp[i-1](i-1번째의 최대 합) + int[i] 한 값이 큰지, 아니면 int[i](본인 값)이 큰지 두 가지만 비교해서 큰 값을 dp[i]로 초기화해주면 됨
그러면 dp에는 i번째까지 왔을 때 최대 합이 하나씩 저장될거고, 여기서 가장 큰 값을 return해주면 됨