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
nis the sum of 1 ton, or (n * (n + 1)) / 2. In asymptotic analysis, that isO(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).
