algorithm - 动态规划 : Find longest subsequence that is zig zag using only one dp array

Question

这道题可以只用一个 dp 数组来完成吗？这是来自 topcoder ( http://community.topcoder.com/stat?c=problem_statement&pm=1259&rd=4493 ) 的之字形问题如果连续数字之间的差异严格在正负之间交替，则数字序列称为之字形序列。第一个差异(如果存在)可能是正数或负数。少于两个元素的序列通常是锯齿形序列。

例如，1,7,4,9,2,5 是锯齿形序列，因为差值 (6,-3,5,-7,3) 交替为正负。相反，1,4,7,2,5 和 1,7,4,5,5 不是之字形序列，第一个是因为它的前两个差是正的，第二个是因为它的最后一个差是零。

给定一个整数序列 sequence，返回 sequence 的最长子序列的长度，即锯齿形序列。子序列是通过从原始序列中删除一些元素(可能为零)而获得的，其余元素保持原始顺序。

Answer 1

供引用:具有两个数组的 DP 使用数组 A[1..n]，其中 A[i] 是以元素 i 上的锯齿形结尾的之字形序列的最大长度，以及数组 B[1 ..n] 其中 B[i] 是以元素 i 上的折线结尾的折线序列的最大长度。对于从 1 到 n 的 i，此 DP 使用 A 数组的先前条目来计算 B[i]，并使用 B 数组的先前条目来计算 A[i]。以额外循环为代价，可以按需重新创建 B 条目，从而仅使用 A 数组。不过，我不确定这是否能解决您的问题。

(此外，由于输入数组非常短，因此有许多编码技巧不值得一提。)