문제 링크
https://leetcode.com/problems/maximum-subarray/동적 프로그래밍이란?
복잡하게 반복되는 sub problems들을 나누고 그 값을들 저장해두었다가 재사용하는 알고리즘카데인 알고리즘이란?
동적 프로그래밍을 사용하는 알고리즘이면서 최대 부분합을 O(n)의 시간 복잡도로 구하는 알고리즘소스 코드
function maxSubArray(nums: number[]): number {
let result = Number.MIN_SAFE_INTEGER;
let sum = 0;
for(let i=0; i<nums.length; i+=1) {
sum += nums[i];
if(result < sum) result = sum;
if(sum < 0) sum =0;
}
return result;
};
result에 Number.MIN_SAFE_INTEGER 을 이용하여 최소값을 할당한다 ( 이것을 최대합값으로 사용할 예정)sum이라는 변수를 0으로 초기화한다배열을 순회하여 순차적으로 하나씩 다 더해줘 sum에 넣는다sum이 result값보다 크면은 result에 sum 값을 넣는다만약 여러 마이너스 값들을 순회해서 sum이 음수가 되어버린다면 다시 0으로 초기화 해준다반복문이 끝난 결과값을 리턴한다