前作以最大子序列和问题为起点,引出了动态规划思想的核心框架。今日恰逢构建之法群里,讨论起一个股票买卖问题,我用动态规划解决了。和邹欣老师的交流中,我进一步发现,引入状态机后,实际上股票买卖问题是最大子序列和问题的扩展。并且,这样的扩展可以更进一步地接近动态规划的核心,因此续作此篇,讨论一下动态规划与状态机。

阅读全文 »

有段时间没写 LaTeX 相关的文章了,此篇讲一讲 xeCJK 宏包中的 Mapping 功能。

由于中文空心句号是一个小圈,容易与作为下标的数字 0 或字母 o 混淆。因此,在专业数学书籍、论文排版中,最好是使用实心句点 来代替中文空心句号。但是,使用中文空心句号编写中文 LaTeX 手稿是大家的习惯;这样一来,使用查找替换固然是一个方案,但是繁琐且容易出错。这时候,我们就可以用到 xeCJK 宏包提供的 Mapping 选项。

Mapping 实际上是借助了 TECKit 来做字符映射。xeCJK 的作者还预先定义了能够实现简体中文和正体中文相互转换的映射表。因此,使用 xeCJK 还能实现中文的简正转换。

阅读全文 »

序列的最大子序列和问题,说的是:给定一个包含若干整数(正负不限)的序列,寻找其中的一个子序列,使得该子序列元素之和在所有子序列的和中最大。

这一经典的问题,可由动态规划(中的 Kadane 算法)在 $O(n)$ 的时间内解决。

如果我们将给定的序列首尾相连,成为一个环状列表。同样的问题,就变得复杂起来。不过,在巧妙的思路下,问题仍然可以在 $O(n)$ 时间内解决。

下面我们先复习一下 Kadane 算法;然后看看怎样在线性时间内,解决循环列表中的最大子序列和问题。

阅读全文 »