We Can Do Better
The above code will complete a scan of every subarray possible. It does so by iterating through every element in the array. Then, at each loop, it tests every subarray with that starting index.
This works but is wildly inefficient. What if there were millions or billions of elements in each array? This caveat can also be understood by the time complexity of the brute force approach. As we are iterative through the array for each given n elements, the time complexity is O(n^2)
. So for a million elements in the array, there will be 10^12
operations which is huge. Perhaps we don't need to test each possible subarray -- so what if we didn't?