Maximum Sum SubArray - Naive Implementation

Question

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).

Answer 1

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.

Answer 2

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

• Yuval Filmus: You can use MathJax to format your math.