💡 풀이
var maxSubArray = function (nums) {
if (nums.length === 1) return nums[0];
let dp = new Array(nums.length).fill(0);
dp[0] = nums[0];
for (let i = 1; i < nums.length; i++) {
let prevMax = dp[i - 1];
let cur = nums[i];
let max = Math.max(cur, prevMax + cur);
dp[i] = max;
}
console.log(dp);
return Math.max(...dp);
};
// 다른 사람의 풀이
var maxSubArray = function (nums) {
let localMax = nums[0];
let finalMax = nums[0];
for (let i = 1; i < nums.length; i++) {
localMax = Math.max(nums[i], localMax + nums[i]);
if (localMax > finalMax) finalMax = localMax;
}
return finalMax;
};
📝 정리
정석적인 DP 문제가 아닌, 변형이 있는 DP 문제였다. Brute force로 푼다면 O(n*n)의 시간 복잡도로 풀 수 있었을 것이다. (모든 부분 배열의 합을 비교함)
카데인 알고리즘(참고 링크)을 이용하면, O(n)의 시간 복잡도로 문제를 풀 수 있다.
카데인 알고리즘을 이용한 풀이를 간단히 설명하면, 이전 인덱스가 가질 수 있는 최대 부분합에 현재의 인덱스 값을 더하면 현재 인덱스가 가질 수 있는 최대 부분합을 구할 수 있음을 의미한다. 만약 이전 인덱스가 가질 수 있는 최대 부분합이 현재의 인덱스 값을 더한 값보다 크다면, 더하지 않고 이전 인덱스가 가질 수 있는 최대 부분합을 유지하면 된다.
이 때문에 let max = Math.max(cur, prevMax + cur) 이와 같은 코드를 작성할 수 있게 된다.
첫 번째 방법은 내가 풀었던 방법이고, 두 번째 방법은 공간 복잡도가 O(1)인 방법이다. 첫 번째 방법과는 달리 기존 nums 배열만을 사용해 문제를 해결하였다.(첫 번째 방법은 dp 라는 배열을 새로 생성했음)
수정, 지적을 환영합니다!
문제 링크
https://leetcode.com/problems/maximum-subarray/
