求数组的最大子数组值和最长公共子序列问题

2025-03-12 23:34:56

推荐回答（1个）

回答1：

a) 最长公共子序列的结构
若用穷举搜索法，耗时太长，算法需要指数时间。
易证最长公共子序列问题也有最优子结构性质
设序列X=和Y=的一个最长公共子序列Z=，则：
i. 若xm=yn，则zk=xm=yn且Zk-1是Xm-1和Yn-1的最长公共子序列；
ii. 若xm≠yn且zk≠xm ，则Z是Xm-1和Y的最长公共子序列；
iii. 若xm≠yn且zk≠yn ，则Z是X和Yn-1的最长公共子序列。
其中Xm-1=，Yn-1=，Zk-1=。
最长公共子序列问题具有最优子结构性质。