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 &lt; arr.length; i++) {
    const startIdx = i;

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

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

      if (max === null || max &lt; 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.