更新
似乎根本不可能做到这一点。有人还给我发了一份不同考试的副本，其中问了几乎相同的问题，但不同的是，你不能从任何位置上删除，只能从开始或开始删除。这个问题很可能是在复制时出错的。现在我只需要证明这一点，并要求重新评估问题考试。
几周前，在一门关于数据结构和算法的课程中，我遇到了以下问题。当时我无法在规定的时间内解决这个问题，尽管我可能会通过课程，但从昨天开始，我一直在努力想出一个解决方案，这样我就可以提高自己的技能。
问题
给定一个整数n，我们从任何位置重复消除一个数字，直到只剩下一个数字。函数PC(n(被定义为通过所描述的过程可获得的整数的最大平方数。
例如PC(32492(=3。两个可能的序列是：
- 32492->3249->324->24->4
- 32492->3249->349->49->9
现在设计一个算法，可以在d的多项式时间内计算PC(n(，其中d是n中的位数。假设你有一种方法来测试一个数字是否是O(1(时间内整数的平方。
到目前为止我尝试了什么
第一种方法显然是测试每个可能的序列并返回最大值。如果我没有记错的话，这就是O(d！(。
在改进暴力方法的基础上，我添加了一个HashMap，用于存储已经计算的所有值。通过这种方式，我们可以使用O(1(查找来避免必须计算两次相同的值。这显然是对所用实时性的改进，但我很难获得时间复杂性的下限。所以，在我看来，这不是多项式。
我也尝试了一些贪婪算法的方法，但正如预期的那样，我发现(我能想到的(每种算法都有一种情况，它没有做出最佳选择。
如有任何帮助，我们将不胜感激。我试着在网上查找类似的问题，但到目前为止运气不佳。
发布这个答案，这样问题就不会悬而未决了。这似乎是老师的一个错误，不可能。
该问题可能只允许消除第一个或最后一个数字，在这种情况下，可以使用动态编程在O(d^2(中解决该问题。
狡猾，狡猾。找平方的方面是转移注意力，如果你能在O(1)中检查一下，这是一个没有意义的问题。真正的问题是唯一的、有序的子串查找，这似乎可以归结为在与之争论之后查找子序列，也许这是一个技巧问题，目标是表明它不能做到？