Reduction from Maximum Subarray to Distance Product
Jump to navigation
Jump to search
FROM: Maximum Subarray TO: Distance Product
Description
Implications
if: to-time: $O(n^{3-\epsilon})$ for some $\epsilon > {0}$
then: from-time: $O(n^{3-\epsilon})$
Year
1998
Reference
Hisao Tamaki and Takeshi Tokuyama. 1998. Algorithms for the maximum subarray problem based on matrix multiplication. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’98). 446–452.