Return to Revisions

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

Let's say that our input array is 4. We can create 1 contigous subarray of length 4; 2 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.

Time Complexity: Each subarray sum takes O(n) to compute and there are (n * (n + 1)) / 2 subarrays hence asymptotic time, O(n^3) i.e n((n * (n + 1)) / 2)

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