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

Question

我需要用 DP 解决这个问题，问题是:我们有一个数组，我们想创建一个具有最大大小的升序子数组，有 2 个条件:

1. 我们可以只从左到右遍历数组一次。
2. 我们只有两个有效的步骤来制作这个子数组:
   • 我们可以在遍历中忽略数组中的下一个元素
   • 我们可以将下一个元素放在数组的末尾或开头，并且该数组必须按升序排列

例如:

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

输出:5

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

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

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

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)