0
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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
$\endgroup$
  • $\begingroup$ You can use MathJax to format your math. $\endgroup$ – Yuval Filmus May 27 '20 at 11:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.