How to use max subarray and algorithm in C++

How to use the maximum subarray sum algorithm in C

The maximum subarray sum problem is a classic algorithm problem, which requires that in a given integer array Find a contiguous subarray such that the sum of all elements in the subarray is maximum. This problem can be solved using the idea of ​​dynamic programming.

A simple but inefficient solution is to find all possible subarrays by exhaustive method, calculate their sum, and then find the largest sum. The time complexity of this method is O(n^3), which will be very slow when the array length is large.

A more efficient solution is based on the idea of ​​dynamic programming. We can record the maximum subarray sum ending with each element by defining an auxiliary array dp. dp[i] represents the largest subarray sum ending with the i-th element. For dp[i], there are two situations:

1. If dp[i-1] is greater than 0, then dp[i] = dp[i-1] arr[i];
2. If dp[i-1] is less than or equal to 0, then dp[i] = arr[i].

We calculate each element of the dp array by traversing the entire array, and simultaneously update the largest subarray and max_sum and the corresponding start and end subscripts start and end. When a larger subarray sum is found, we update the corresponding value. Finally, the maximum subarray sum is max_sum, and the starting subscript of the subarray is start and the ending subscript is end.

The following is a code example to implement the maximum subarray sum algorithm in C language:

#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;
}

Run the above code, the output result is as follows:

Maximum subarray sum: 6
Start subscript of subarray: 3
End subscript of subarray: 6

The above code solves the maximum subarray sum with O(n) time complexity through the idea of ​​dynamic programming. question. This algorithm is very efficient when dealing with large arrays.

The above is the detailed content of How to use max subarray and algorithm in C++. For more information, please follow other related articles on the PHP Chinese website!