从只有 3 个有效移动的数组制作最大长度升序子数组

Question

我需要用DP解决这个问题，问题是：我们有一个数组，我们想制作一个最大尺寸的升序子数组，有两个条件：

我们只需要从左到右遍历一次数组即可。
我们只有两个有效的移动来制作这个子阵列：
- 我们可以在遍历中忽略数组中的下一个元素
- 我们可以将下一个元素放在数组的末尾或开头，并且该数组必须按升序排列

例如：

输入：arr[ ] = {0 , 3 , 10 , 7 , 6 , 5 , 14}

输出：5

子数组是{5 , 6, , 7 , 10 , 14}

这个例子的解决方案是，从10开始，然后在左边放7，在左边放6和5，然后在10的右边放14

也就是说我们可以通过这个条件从左向右扩展数组

Answer 1

这是一个经典的 dp 问题，使用自上而下的方法非常简单。

让我们定义我们的状态 dp[c][dec][inc] - 我们现在正在查看位置 c 处的元素，我们构建的序列后面的元素位于位置 dec，而位于序列的前面在位置 inc.

所以现在我们可以遍历到：

dp[c+1][dec][inc] 跳过当前元素
dp[c+1][c][inc] 通过将当前元素放在后面（仅当 a[c] <= a[dec] 时有效）
dp[c+1][dec][c] 通过将当前元素放在前面（仅当 a[c] >= a[inc] 时有效）

示例代码（C++）：

const int n = 7;
int a[] = {0, 0, 3, 10, 7, 6, 5, 14};
int dp[n+1][n+1][n+1];

int solve(int c, int dec, int inc)
{
    if(c > n)return 0;
    if(dp[c][dec][inc] != -1)return dp[c][dec][inc];

    dp[c][dec][inc] = solve(c+1,dec,inc); //skip element
    if(inc==0 && dec==0) //if our sequence is empty, try appending element to sequence
        dp[c][dec][inc] = max(dp[c][dec][inc], 1 + solve(c+1,c,c));
    else if(a[c] >= a[inc])//we can extend our array [dec, ..., inc] because current element can be put to front
        dp[c][dec][inc] = max(dp[c][dec][inc], 1 + solve(c+1,dec,c));
    else if(a[c] <= a[dec])//we can extend our array [dec, ..., inc] because current element can be put to back
        dp[c][dec][inc] = max(dp[c][dec][inc], 1 + solve(c+1,c,inc));

    return dp[c][dec][inc];
}

int main()
{
    memset(dp, -1, sizeof dp);
    cout<<solve(1,0,0);
}

复杂度 O(n^3)

从只有 3 个有效移动的数组制作最大长度升序子数组

Making Maximum Length Ascending Sub array from an array with only 3 valid moves

arrays

algorithm

dynamic-programming

maxlength

sub-array