Leetcode에서 Maximum Subarray 풀어보기

문제 링크

bookmark

동적 프로그래밍이란?

• 복잡하게 반복되는 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으로 초기화 해준다
• 반복문이 끝난 결과값을 리턴한다