Home >Backend Development >C++ >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:
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!