假设我们有一个给定长度的整数序列n.我们想要删除一些元素(可能没有),以便序列在结果中轮流增加和减少.这意味着,每个元素都应该具有相邻元素,既可以更大,也可以比自身小.例如1 3 2 7 6,5 1 4 2 10两个序列都是轮流增加和减少的.我们想要删除一些元素来转换我们的序列,但我们也希望最大化剩余元素的总和.因此,例如,从序列中2 18 6 7 8 2 10我们想要删除6并制作它2 18 7 8 2 10.
我正在寻找一个有效的解决方案来解决这个问题.上面的例子表明,最天真的贪婪算法(删除每个破坏序列的第一个元素)将不起作用 - 它将删除7而不是6,这将不会最大化剩余元素的总和.任何想法如何有效(O(n) or O(n log n)可能)和正确解决？
我们给出方数矩阵,例如
1 9 2
3 8 3
2 1 1
相邻数字之间的距离是2.我们希望在同一行或同一列中找到这样的两个数字,它们的总和加上它们之间的距离是最大的.例如,在上面的示例中,这些数字是9和8,并且最大结果是9+8+1*2 = 19.我们想要找到最大的结果,我们不需要具体的数字.
对我来说这看起来像是一个DP问题,但我想不出任何优雅的解决方案.