Solution Review: Maximum Subarray Sum

This review discusses the solution of the Maximum Subarray Sum Challenge in detail.

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 iith elements, and calculates their sum
  • A maxmax 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 O(n2)O(n^2) 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 O(nLogn)O(nLogn) time. Following is the Divide and Conquer algorithm:

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.