# Maximum Sum SubArray - Naive Implementation

I am looking at a problem that is often asked in interview settings. The problem statement is:

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

I want to talk about the naive solution, where we generate all contigous subarrays, take their sums, and find the maximum sum. Here is an implementation of the naive solution:

function maxSubArray(arr) {
let max = null;

for (let i = 0; i < arr.length; i++) {
const startIdx = i;

for (let j = i; j < arr.length; j++) {
let sum = 0;

for (let k = i; k <= j; k++) {
sum = sum + arr[k];
}

if (max === null || max < sum) {
max = sum;
}
}
}

return max;
}



I know that this solution runs in O(n^3), but I do not understand why that is the case. If we "generate" all possible contigous subarrays, I can explain why that is an O(n^2) operation:

Let's say that our input array is 4. We can create 1 contigous subarray of length 4; 3 contigous subarrays of length 3; 3 contigous subarrays of length 2, and 4 contigous subarrays of length 1. In other words, the number of contigous subarrays for an array of length n is the sum of 1 to n, or (n * (n + 1)) / 2. In asymptotic analysis, that is O(n^2).

Now, I understand that summing up each individual subarray is **not* free, but here is where I am stuck. I do not know how to "add the work that we do to get the sum of each subarray" to my existing time complexity of O(n^2).

An implementation that I wouldn't call naïve but criminally stupid would calculate the sum of elements in each subarray by adding up the elements. You are summing from 1 to n elements for each of n^2/2 subarrays, which makes it $$O (n^3)$$ (proving that this is a lower bound needs a bit more care).

Of course a naïve but not stupid implementation would calculate the sums for all subarrays starting with the first element using only one extra addition for each sum.

I will quote part of your answer with a slight correction:

Let's say that our input array is 4. We can create 1 contiguous subarray of length 4; 2 contiguous subarrays of length 3; 3 contiguous subarrays of length 2, and 4 contiguous subarrays of length 1. In other words, the number of contiguous subarrays for an array of length $$n$$ is the sum of $$1$$ to $$n$$, or $$n(n+1)/2$$.

Time Complexity: Each subarray sum takes $$O(n)$$ to compute and there are $$n(n+1)/2$$ subarrays, hence the asymptotic time is $$O(n\cdot n(n+1)/2) = O(n^3)$$.

See inline comments in your code too:

function maxSubArray(arr) {
let max = null;

for (let i = 0; i < arr.length; i++) { // O(n)
const startIdx = i;

for (let j = i; j < arr.length; j++) { // O(n)
let sum = 0;

for (let k = i; k <= j; k++) { // O(n)
sum = sum + arr[k];
}

if (max === null || max < sum) {
max = sum;
}
}
}

return max;
}


For example if $$\mathrm{arr} = [4, -1, 2, 1]$$, notice that at some point we do traverse the entire array of length $$n$$:

subarray, sum
[4], 4
[4, -1], 3
[4, -1, 2], 5
[4, -1, 2, 1], 6
[-1], -1
[-1, 2], 1
[-1, 2, 1], 2
[2], 2
[2, 1], 3
[1], 1

max_sum = 6

• You can use MathJax to format your math. May 27 '20 at 11:23