We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
The runtime analysis on this is surprising to me; insert (ie bisect.insort) is O(n)[1] so it reads as though this solution is ~O(n^2), but emprically performs much better than the naive solution doing a simple comparison of all (i,j) pairs.
Would love to hear more thoughts or be corrected here, at first blush this solution feels somewhat like "getting away" with ignoring the BST hoops other languages have to jump through.
Maximum Subarray Sum
You are viewing a single comment's thread. Return to all comments →
Impressive solution, thanks for sharing.
The runtime analysis on this is surprising to me; insert (ie bisect.insort) is O(n)[1] so it reads as though this solution is ~O(n^2), but emprically performs much better than the naive solution doing a simple comparison of all (i,j) pairs.
Would love to hear more thoughts or be corrected here, at first blush this solution feels somewhat like "getting away" with ignoring the BST hoops other languages have to jump through.
[1] https://wiki.python.org/moin/TimeComplexity