如何检查一个数组是否是另一个数组的子序列？
问题内容：
我正在寻找探索递归和动态编程的不同算法，这些算法检查一个arrayA是否为arrayB的子序列。例如，
arrayA = [1, 2, 3]
arrayB = [5, 6, 1, 7, 2, 9, 3]
thus, arrayA is indeed a subsequence of arrayB.
我尝试了几种不同的搜索，但是似乎只能找到计算最长增长子序列的算法。
问题答案：
由于您必须将的 所有 元素匹配arrayA到的某些元素arrayB，因此您无需 回溯
。换句话说，如果有两个arrayB与的元素匹配的候选者arrayA，则可以选择最早的一个，而从不撤消选择。
因此，您不需要DP，因为可以使用简单的线性贪心策略：
bool isSubsequence(int[] arrayA, int[] arrayB) {
int startIndexB = 0;
foreach (int n in arrayA) {
int next = indexOf(arrayB, startIndexB , n);
if (next == NOT_FOUND) {
return false;
}
startIndexB = next+1;
}
return true;
}
