为了描述方便,我用图论的说法讲了。
我们先把 增加一,把原数组用两个
套起来,这样我们就必须把数组用完了。
节点对应卡片,节点编号对应卡片序号。
第一步,我们先对于任何一个节点,向编号下一个节点连一个边权为“随意”的边。
我们从两张卡片间隔小到大的卡片一次考虑,每一次考虑,我们计算从这种卡片的前面的一张所对应的节点和这种卡片后面的一张的紧接着的后面的卡片对应的点的最长路(其中,“随意”边权的边在这一轮计算时被当做边权为卡片上面的数字的边),计算完最长路后,我们从这种卡片的前面的一张所对应的节点到这种卡片后面的一张的紧接着的后面的卡片对应的点连接一个边权为最长路的边。
号卡片对应的最长路就是答案。