假设我们给出了一个整数输入数组,如何找到满足以下条件的最长凸子序列:
c[i] < (c[i-1] + c[i+1]) / 2
c[i-1],c[i]并且c[i+1]是子序列中的三个连续元素.
例如,如果输入数组是{ 1, 2, -1, 0, 3, 8, 5 },则最长的凸子序列应为:{ 1, -1, 0, 3, 8 }或{ 2, -1, 0, 3, 8 }.
我试图在"最长增加子序列"(LIS)问题中使用相同的动态编程思想来解决这个问题.但是因为子序列中的每个元素都依赖于前两个元素,所以似乎O(n ^ 2)解决方案是不可能的.谢谢您的帮助.
如果不存在S的不同元素x和y使得x可被y整除,则称正S的正整数为"无分裂".例如,S = {2,3,5}是无分割的,但是{2,3,4,5}不是,因为4可以被2整除.你将如何计算{1,2,...的最大子集. ..,n}这是免费的吗？例如,当n = 10时,则T = {4,6,7,9,10}是最大除法子集之一.
我小学的侄子问我这个看似简单的数学问题.我只能想到蛮力方法.但是当n很大时会变得很难看.是否有一个不错的算法来解决它的计算机？
谢谢.
algorithm ×2