Solution: Maximum Subarray Sum

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 $i$th elements, and calculates their sum
• A $max$ 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(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)$ time. Following is the Divide and Conquer algorithm: