Kadane의 알고리즘을 사용한 최대 하위 배열 합계 문제 설명

FAANG이나 대기업에 취직하고 훌륭한 프로그래머가 되기 위해 동적 프로그래밍 관련 문제를 해결하는 것 외에 다른 대안은 없습니다. 우리 개발자들은 종종 문제 해결을 무시하고 개발에만 집중하려고 하지만 실생활의 큰 생산 문제를 해결하거나 무언가를 최적화하려면 아주 좋은 문제 해결사가 되어야 한다는 것을 기억해야 합니다. 이것은 일상적인 직업에서 문제를 해결하는 데 많은 도움이 될 것입니다.

그래서 이 점을 염두에 두고 동적 프로그래밍 관련 문제를 해결하기 시작했고 처음에는 Kadane의 알고리즘으로 쉽게 해결할 수 있는 The Maximum Subarray Sum 문제에 대해 알게 되었습니다. 오늘 저는 이 알고리즘에 대해 논의하고 이를 통해 문제를 해결하고자 합니다.

먼저 문제에 대한 설명을 알려주십시오. 그것은 말한다

We are given an integer array, we need to find the contiguous subarray that has the largest sum and return that sum. For example: [-2,1,-3,4,-1,2,1,-5,4] is an array. Here the subarray [4,-1,2,1] has the largest sum which is 6.

이제 Kadane의 알고리즘이 말하는 것을 살펴보겠습니다.

2개의 변수를 current_sum를 0으로, max_sum를 현재 위치의 합계와 해당 배열의 최대 합계를 나타내는 최소 음수 값으로 초기화합니다.

현재 배열 요소와 current_sum가 있는 해당 요소의 합계 사이의 최대값을 current_sum로 할당합니다.

max_sum와 current_sum 사이의 최대값을 max_sum로 할당합니다.

배열의 모든 요소에 대해 2단계와 3단계를 반복합니다.

max_sum 를 반환합니다.

여기서 나는 C++로 문제를 해결하고 싶지만 당신은 어떤 언어를 선택할 자유가 있습니다.

int findMaxSum(vector<int>& nums) {
    int max_sum = INT_MIN;
    int current_sum = 0;

    for(int n:nums) {
        current_sum = max(n, current_sum + n);
        max_sum = max(max_sum, current_sum);
    }

    return max_sum;
}

aaray의 총 요소 수인 n번 동안 실행되는 단일 루프가 있으므로 실행 시간 복잡도는 O(n)입니다. 동시에 외부 데이터 구조가 필요하지 않기 때문에 공간 복잡도는 O(1)입니다.

따라서 Kadane의 알고리즘을 사용하여 최대 하위 배열 합계 문제를 해결했습니다. 이제 우리의 접근 방식이 동적 프로그래밍과 어떻게 유사한지 살펴보겠습니다. 동적 프로그래밍 방식에서는 주요 문제를 더 작은 문제 그룹으로 나누고 이러한 작은 문제의 각 솔루션을 다시 활용하여 다시 계산할 필요가 없도록 하는 메모이제이션(memoization)이라고 합니다. 여기에서 각 배열 요소와 현재 합계 사이의 최대값을 계산하고 해당 요소 인덱스의 현재 합계로 최대값을 할당했습니다. 그런 다음 해당 위치의 현재 합계와 최대 합계를 비교하고 그 사이의 최대값을 최대 합계로 할당했습니다. 따라서 모든 단계에서 문제를 해결하고 이전에 계산한 결과를 다시 활용했습니다. 따라서 우리는 솔루션에서 동적 프로그래밍 접근 방식을 사용했습니다.

동적 프로그래밍 접근 방식을 이해하고 구현하는 것은 매우 어렵지만 정기적인 연습과 약간의 노력을 통해 달성할 수 있습니다. 나는 우리가 아주 좋은 개발자가 되기 위해 문제 해결을 시작하기를 바랍니다.

즐거운 코딩!!!