C++에서 최대 하위 배열 및 알고리즘을 사용하는 방법

C++에서 최대 하위 배열 합 알고리즘을 사용하는 방법

최대 하위 배열 합 문제는 모든 하위 배열 요소의 합이 다음과 같이 주어진 정수 배열에서 연속적인 하위 배열을 찾아야 하는 고전적인 알고리즘 문제입니다. 가장 큰. 이 문제는 동적 프로그래밍이라는 아이디어를 사용하여 해결할 수 있습니다.

간단하지만 비효율적인 해결책은 철저한 방법으로 가능한 모든 하위 배열을 찾고 그 합을 계산한 다음 가장 큰 합을 찾는 것입니다. 이 방법의 시간 복잡도는 O(n^3)이며, 배열 길이가 길면 속도가 매우 느려집니다.

보다 효율적인 솔루션은 동적 프로그래밍 아이디어를 기반으로 합니다. 보조 배열 dp를 정의하여 각 요소로 끝나는 최대 하위 배열 합계를 기록할 수 있습니다. dp[i]는 i번째 요소로 끝나는 가장 큰 하위 배열 합계를 나타냅니다. dp[i]의 경우 두 가지 상황이 있습니다.

1. dp[i-1]이 0보다 큰 경우 dp[i] = dp[i-1] + arr[i]
2. If dp[i -1 ]이 0보다 작거나 같으면 dp[i] = arr[i]입니다.

전체 배열을 순회하여 dp 배열의 각 요소를 계산하고 가장 큰 하위 배열과 max_sum, 해당 시작 및 끝 첨자 start 및 end를 동시에 업데이트합니다. 더 큰 하위 배열 합계가 발견되면 해당 값을 업데이트합니다. 마지막으로, 최대 하위 배열 합은 max_sum이고 하위 배열의 시작 첨자는 start이고 끝 첨자는 end입니다.

다음은 C++ 언어로 최대 하위 배열 및 알고리즘을 구현하는 코드 예제입니다.

#include <iostream>
#include <vector>

using namespace std;

vector<int> maxSubarraySum(vector<int>& arr) {
    int n = arr.size();
    int dp[n];
    dp[0] = arr[0];
    int max_sum = dp[0];
    int start = 0, end = 0;

    for(int i = 1; i < n; i++) {
        if(dp[i-1] > 0)
            dp[i] = dp[i-1] + arr[i];
        else {
            dp[i] = arr[i];
            start = i;
        }
        
        if(dp[i] > max_sum) {
            max_sum = dp[i];
            end = i;
        }
    }
    
    vector<int> result;
    result.push_back(max_sum);
    result.push_back(start);
    result.push_back(end);

    return result;
}

int main() {
    vector<int> arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    vector<int> result = maxSubarraySum(arr);
    
    cout << "最大子数组和：" << result[0] << endl;
    cout << "子数组的起始下标：" << result[1] << endl;
    cout << "子数组的终止下标：" << result[2] << endl;

    return 0;
}

위 코드를 실행하면 출력 결과는 다음과 같습니다.

최대 하위 배열 합계: 6
하위 배열의 첨자 시작: 3
of the subarray Termination subscript: 6

위 코드는 동적 프로그래밍 아이디어를 통해 O(n) 시간 복잡도를 갖는 최대 하위 배열 합 문제를 해결합니다. 이 알고리즘은 대규모 배열을 처리할 때 매우 효율적입니다.

위 내용은 C++에서 최대 하위 배열 및 알고리즘을 사용하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!