[C] LeetCode 53. Maximum Subarray

 

문제(원문)

문제(번역)

정수 배열 nums가 주어질 때, 부분수열의 합 중 가장 큰 합을 구하고 반환해라.

접근 방법

대표적인 DP문제다. (물론 divide and conquer 방식으로도 풀 수 있지만 코드가 복잡해진다..)

현재 원소 이전까지의 합에 현재 원소를 더한 값과 현재 원소 중 더 큰 값을 저장해가면서 가장 큰 부분 수열의 합을 구하면 된다.

 

소스 코드

int max(int a, int b) { return (a>b) ? a : b; }

int maxSubArray(int* nums, int numsSize) {
    int dp[100002] = {0};
    int m = nums[0];
    dp[0] = nums[0];
    for(int i = 1; i<numsSize; i++) {
        dp[i] = max(dp[i-1] + nums[i], nums[i]);
        m = max(m, dp[i]);
    }
    return m;
}

이러면 추가 공간 배열이 필요하므로 공간복잡도는 O(n)이 될 것이다.

또한 배열을 한번 순회하므로 시간복잡도는 당연히 O(n)이 된다.