问题描述
假设给定一个整数输入数组，如何找到满足以下条件的最长凸子序列：
Suppose we are given an input array of integers, how to find the longest convex subsequence that satisfies the following condition:
c[i] < (c[i-1] + c[i+1]) / 2
c [i-1] ， c [i] 和 c [i + 1] 是子序列中的三个连续元素。
c[i-1], c[i] and c[i+1] are three consecutive elements in the subsequence.
例如，如果输入数组为 {1，2，-1，0，3 ，8，5，} ，最长凸子序列应为： {1，-1，0，3，8} 或 {2，-1，0，3，8} 。
For example, if input array is { 1, 2, -1, 0, 3, 8, 5 }, the longest convex subsequence should be: { 1, -1, 0, 3, 8 } or { 2, -1, 0, 3, 8 }.
我试图使用相同的动态编程思想来解决此问题最长增加子序列（LIS）问题。但是由于子序列中的每个元素都取决于前两个元素，因此似乎不可能实现O（n ^ 2）解。感谢您的帮助。
I tried to solve this problem using the same dynamic programming idea in "Longest Increasing Subsequence" (LIS) problem. But because each element in the subsequence depends on the previous two elements, it seems that an O(n^2) solution is impossible. Thank you for your help.
推荐答案
让最长的凸序列称为LCS； N> 1的最小长度为2。下面的算法不言自明。
Lets call the longest convex sequence as LCS; The minimum possible length for N>1 is 2. The algo below is self explanatory.
int LCS[N];
LCS[0] = 1; LCS[1] =2 ;
for(i=2;i<N;i++)
{
LCS[i] = 2;
for(j=1;j<i;j++)
{
for(k=0;k<j;k++)
{
if(LCS[j]-1 == LCS[k] && A[j] < (A[k] + A[i])/2 )
LCS[i] = max( LCS[i], 1+LCS[j]);
}
}
}
这篇关于数组中最长的凸子序列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！