연속합

문제

• 백준 1912번 - 연속합

언어

• JavaScript

문제 풀이 step 1

• dp[n] = n번째 수가 마지막으로 오는 연속합 중의 가장 큰 합
• DP의 특징인 작은 문제의 해답으로부터 큰 문제의 해답을 찾는다를 이용합니다.
• 마지막 단계인 n번째를 생각해볼 때, 그 앞의 n-1 즉 dp[n-1]은 n-1번째 수를 포함하는 가장 큰 연속합입니다.
• 그렇다면 n번째 수 입장에서
  • 앞의 연속된 수들의 합에 연속되는 것이 큰지
  • 앞의 연속된 수들의 합에 연속되지 않는 것이 큰지
• 위와 같이 2가지 경우를 찾아낼 수 있습니다.
• 따라서, dp[n] = Math.max(dp[n-1] + arr[i], arr[i])

소스 코드

const input = require("fs").readFileSync("/dev/stdin").toString().split("\n");

const solution = (input) => {
	const n = parseInt(input[0]);
	const arr = input[1].split(" ").map(Number);

	// base
	const dp = [arr[0]];
	for (let i = 1; i < n; i++) {
		dp[i] = Math.max(arr[i], dp[i - 1] + arr[i]);
	}

	return Math.max(...dp);
};

console.log(solution(input));