Given an integer array nums, find the subarray with the largest sum, and return its sum.
Example 1:
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.
Example 2:
Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.
Example 3:
Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.
문제
배열이 주어지면 하위 배열들의 합이 제일 큰 수를 출력해야 함
subbarray는 위와 같은 방식
시간복잡도를 O(n)으로 해야하기 때문에 무차별 대입방식으로 상위 배열과 하위배열을 계산하면 2번 중첩되기 때문에 중첩되지 않은 반복문으로 해당 답을 구하여야 함
이 문제를 해결하는 다양한 방법중에 카데인 알고리즘이 있는데, 현재 부분합의 최대값이 이전의 부분합의 최대값 반영된 결과값이라는 것이다.
위 이미지는 무차별 대입방식을 거꾸로 했을때의 모습인데 이 방법을 이용해서 필요한 부분만 계산을 하게된다.
var maxSubArray = function(nums) {
let l = nums[0];
let g = nums[0];
for (i=1; nums.length>i; i++) {
l = Math.max(nums[i], l+nums[i]);
if (l > g) {
g = l;
}
}
return g;
};
참고문서 : Kadane’s Algorithm — (Dynamic Programming) — How and Why does it Work?
