The problem Maximum Subarray is a classic coding challenge that asks you to find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
For example, given an array of numbers like [-2,1,-3,4,-1,2,1,-5,4], the maximum subarray is [4,-1,2,1] which has a sum of 6.
Here are some common ways to solve this problem implemeted in C++:
This is the most straightforward approach, where you consider all possible subarrays and calculate their sums. The maximum sum among all these subarrays is the answer. This approach has a time complexity of O(n^2) as you have to check all possible subarrays.
#include <iostream>
#include <vector>
using namespace std;
int maxSubArray(vector<int> &nums) {
int n = nums.size();
if (n == 0) {
return 0; // Edge case: empty array
}
int maxSum = nums[0];
for (int i = 0; i < n; ++i) {
int currentSum = 0;
for (int j = i; j < n; ++j) {
currentSum += nums[j];
if (currentSum > maxSum) {
maxSum = currentSum;
}
}
}
return maxSum;
}
int main() {
vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
int result = maxSubArray(nums);
cout << "Maximum subarray sum is: " << result << endl;
return 0;
}
// Output:
// Maximum subarray sum is: 6Kadane’s algorithm is an efficient and widely-used approach. It maintains two variables, one to keep track of the current maximum subarray sum and another to keep track of the maximum subarray sum seen so far. It iterates through the array once, updating these variables as it goes. This approach has a time complexity of O(n).
#include <iostream>
#include <vector>
using namespace std;
int maxSubArray(vector<int> &nums) {
int n = nums.size();
if (n == 0) {
return 0; // Edge case: empty array
}
int maxEndingHere = nums[0];
int maxSoFar = nums[0];
for (int i = 1; i < n; ++i) {
maxEndingHere = max(nums[i], maxEndingHere + nums[i]);
maxSoFar = max(maxSoFar, maxEndingHere);
}
return maxSoFar;
}