Solution Review: Maximum Subarray Sum
This review discusses the solution of the Maximum Subarray Sum Challenge in detail.
We'll cover the following
Solution # 1
A naive solution to this problem is to find the sum of all possible contiguous subarrays, find the maximum of those sums, and return that sum. This approach can easily be implemented using two for-loops like this:
for(int i = 0; i < n; i++) {
int sum = 0;
for (int j = i; j < n; j++) {
sum += a[j];
if (sum > max)
max = sum;
}
}
- The outer loop goes through each element one by one, picking the starting element
- The inner loop goes through all the possible successive combinations of th elements, and calculates their sum
- A variable is replaced if a greater sum is found at any point in the nested loop structure
Time Complexity
As you might have guessed, this approach takes time to run because of the two for-loops.
Solution # 2 (Efficient)
Using Divide and Conquer approach, we can find the maximum subarray sum in time. Following is the Divide and Conquer algorithm:
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.