[BOJ 1912] 연속합

문제

연속합

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

 

 

풀이

설명

n개의 정수로 이루어진 수열에서, 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 값을 구하는 문제입니다.

 

DP를 통해 해결할 수 있습니다.

 

dp[i]는 i번째 수를 마지막으로 포함했을 때 구할 수 있는 최댓값입니다.

 

정수 배열을 nums라고 할 때,

dp[i]의 값은 다음 두 가지 중 더 큰 값입니다.

• dp[i -1] + nums[i]
• nums[i]

 

예시 코드

function solution() {
  const n = Number(input());
  const nums = input().split(" ").map(Number);
  const dp = [nums[0]];

  for (let i = 1; i < n; i++) {
    dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
  }

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