View source for Reduction from Maximum Subarray to Distance Product

FROM: [[Maximum Subarray]] TO: [[Distance Product]]

== Description == 



== Implications == 

if: to-time: $O(n^{3-\epsilon})$ for some $\epsilon > {0}$<br/>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.

https://dl.acm.org/doi/abs/10.5555/314613.314823