双调序列(Bitonic Sequence)的定义:双调序列是一个先单调递增后单调递减的序列,即存在两种单独特性,故为“双调”。...从数学角度而言,对于序列(a[0],a[1],…,a[n-1]):
(1)如果存在索引号j,其中0≤j是单调递增,同时(a[j],…,a[n-1])是单调递减的...;
(2)在条件(1)无法满足的情况下,如果存在索引号i,且0≤i<n,使得(a[i],…,a[n-1],a[0],…,a[i-1])满足条件(1)
换言之,序列本身先单调递增后单调递减或者序列经过循环移位后先单调递增再单调递减...但其实下面几种情形都是双调序列,图①和图②不再赘述。图③“升->降->升”,通过循环移位即可变为先单调递增再单调递减序列。图④“降->升->降”,仍可通过循环移位变为先单调递增再单调递减序列。...需要注意的是完全单调递增或者完全单调递减的序列也是双调序列,例如(0,1,4,5)和(7,5,3)均为双调序列。
双调序列的性质:
(1)双调序列的子序列仍为双调序列。