擅长:python、mysql、java
<p>有一个漂亮的解决方案,其运行时间与M无关</p>
<p>在下图中,第一行表示初始序列。在第二行中,我们有从左到右的1、2、…M个连续元素组的最大值(“前缀”最大值)。在第三行,我们有从右到左的1,2,…M个连续元素组的最大值(“后缀”最大值)。第四行是第二行和第三行元素的最大值</p>
<pre><code>a b c d e f g h i j k l m n o
a ab abc d de def g gh ghi j jk jkl m mn mno
abc bc c def ef f ghi hi i jkl kl l mno no o
abc bcd cde def efg fgh ghi hij ijk jkl klm lmn mno
</code></pre>
<p>注意,第三行中有复制的元素,我们不需要计算它们</p>
<p>第二行的计算对M个元素的每个切片进行M-1次比较;第二行是M-2,第三行是M。因此忽略末尾的影响,我们对每个元素执行的比较略少于3次</p>
<p>所需的存储是一个额外的M元素数组,用于临时评估第三行的切片</p>