算法作业4

Python

分治思路

将待处理骨牌中，找到一个中间牌，将中间牌（$S_k$）两侧的牌各分为1组，分别求$\sum_1^{k-1}R[i]\cdot L[i+1]$ 与 $\sum_{k+1}^{n-1}R[i]\cdot L[i+1]$的最大值，并记录各组所有元素的旋转状态。

合并思路

$S_k$的旋转状态，按照比较左侧组最后一个牌的右值（R[k-1]）与右侧组第一个牌的左值（L[k+1]），即 MaxNeighbor = Max(R[k-1], L[k+1])。
$S_k$左右2侧的最大值，即Max(L[k], R[k])旋转至MaxNeighbour一侧，合并完成。