Cubic space complexity, how?

How this solution has cubic space complexity in the worst case? Shouldn’t be quadratic in the worst case? In cubic space complexity every subarray should have a subarray of the maximum of N elements which can newer happen in this example?

Hi @Mladen_Milosavljevic

The main for-loop managing the sliding window takes O(N) but creating subarrays can take up to O(N^2) in the worst case. Therefore overall, our algorithm will take O(N^3).

That’s time complexity, my question is related to space complexity.