subarray란 전체 배열안에 연속된 부분 배열을 의미한다. 즉, 전체 배열에서 부분 배열의 가장 큰 합을 구하는 문제이다.
배열에 음수가 없다면, 최대 부분 배열의 합은 전체 배열의 합이다. 배열에 양수가 없다면, 가장 큰 음수 하나이며 조건에 따라 빈 배열이 될 수 있다.
모든 부분 배열의 합을 비교하는 완전 탐색(Brute force)로 문제를 풀었는데, DP(Kadane 알고리즘)로 푼 해설을 보고 알아보았다.
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.
완전 탐색으로 모든 subarray의 합 중 가장 큰 값을 출력할 수 있다. i
와 j
는 모든 부분 배열을 탐색하고 k
는 부분 배열의 합을 구한다. 시간 복잡도는 O(n^3)
이 될 것이다.
var maxSubArray = function(nums) {
if (nums=== null || nums.length === 0) return 0
let maxSum = nums[0]
for (let i = 0; i < nums.length; i++) {
for (let j = i; j < nums.length; j++) {
let currSum = 0;
for (let k = i; k <= j; k++) {
currSum += nums[k];
}
maxSum = Math.max(maxSum, currSum)
}
}
return maxSum
}
maxSubArray([-2,1,-3,4,-1,2,1,-5,4])
위 코드에서 j
를 반복할 때, 합을 누적하면서 비교하면 시간복잡도 O(n^2)
로 개선할 수 있다.
var maxSubArray3 = function(nums) {
if (nums=== null || nums.length === 0) return 0
let maxSum = nums[0]
for (let i = 0; i < nums.length; i++) {
let currSum = 0;
for (let j = i; j < nums.length; j++) {
currSum += nums[j];
maxSum = Math.max(maxSum, currSum)
}
}
return maxSum
}
dp[i]
는 각 i
까지의 누적 합이다. 즉, 현재 인덱스의 누적합은 바로 이전 인덱스 dp[i-1]
와 현재 nums[i]
값의 합이다. 하지만 dp[i-1] + nums[i]
가 현재 nums[i]
보다 작다면 nums[i]
를 dp[i]
에 담는다. (부분 배열의 시작 인덱스를 변경함)
DP는 시간,공간 복잡도 O(n)
를 가진다.
var maxSubArray = function(nums) {
if (nums=== null || nums.length === 0) return 0
let dp = new Array(nums.length).fill(0);
dp[0] = nums[0]
for(let i = 1; i < nums.length; i++) {
dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
}
return Math.max(...dp);
}
dp 배열은
[ -2, 1, -2, 4, 3, 5, 6, 1, 5]
로Math.max(dp[i-1] + nums[i], nums[i])
공식을 적용하면, 3번째 인덱스와 7번째 인덱스에서 nums[i]를 대입하게 된다. 즉, 인덱스 3~6까지[4,-1,2,1]
의 합인6
이 가장 큰 부분배열의 합이 된다.
DP 접근법와 동일한 공식을 가지고 n
만큼의 배열을 만드는 대신 변수에 담아 maxSum
을 변경하는 식으로 공간복잡도를 O(1)
의 상수로 개선할 수 있다. 제안한 이의 이름을 붙여 카데인의 알고리즘(1984)이라고 한다.
var maxSubArray = function(nums) {
let currSum = nums[0];
let maxSum = nums[0];
for (let i = 1; i < nums.length; i++) {
currSum = Math.max(currSum + nums[i], nums[i]);
maxSum = Math.max(currSum, maxSum)
console.log(currSum, maxSum)
}
return maxSum;
};