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$

...