简单区间类型动态规划

简单区间类型动态规划是指，给定一个长度为 n 的数组，求其某个连续子数组的最大/最小值等类型的问题。该问题可以使用动态规划来求解。

以下是使用 C++ 代码演示简单区间类型动态规划的过程，并用数据模拟展示的例子：

假设有一个数组 arr = {5, -6, 8, -7, 10, 2}，要求求出其所有子数组中的最大值。

动态规划的思路是，先定义一个 dp 数组，其中 dp[i] 表示以 arr[i] 结尾的子数组的最大值。那么对于 dp[i]，它可以由 dp[i-1] 和 arr[i] 计算得到。

具体地，考虑以 arr[i] 结尾的子数组的最大值，可能有两种情况：

1. 以 arr[i-1] 结尾的最大子数组加上 arr[i] 仍然比 arr[i] 小，则以 arr[i] 结尾的最大子数组就是 arr[i] 本身；

2. 以 arr[i-1] 结尾的最大子数组加上 arr[i] 比 arr[i] 大，则以 arr[i] 结尾的最大子数组就是以 arr[i-1] 结尾的最大子数组加上 arr[i]。

因此，可以得到状态转移方程为：

dp[i] = max(dp[i-1] + arr[i], arr[i]);

最终的最大子数组和就是 dp 数组中的最大值。

下面是该问题的 C++ 代码实现：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    vector<int> arr = {5, -6, 8, -7, 10, 2};
    int n = arr.size();

    vector<int> dp(n, 0);
    dp[0] = arr[0];
    int res = dp[0];

    for (int i = 1; i < n; i++) {
        dp[i] = max(dp[i-1] + arr[i], arr[i]);
        res = max(res, dp[i]);
    }

    cout << "The maximum sum of subarray is: " << res << endl;

    return 0;
}

输出结果为：

The maximum sum of subarray is: 15

这说明，原数组 arr 的最大子数组和为 15，即 {8, -7, 10, 2}。

以下是使用 C++ 代码演示简单区间类型动态规划的过程，并用数据模拟展示的完整示例：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    // 输入数据
    int n;
    cin >> n;
    vector<int> a(n+1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    // 初始化 dp 数组
    vector<vector<int>> dp(n+1, vector<int>(n+1));
    for (int i = 1; i <= n; i++) {
        dp[i][i] = a[i];
    }

    // 状态转移
    for (int len = 2; len <= n; len++) {
        for (int i = 1; i <= n - len + 1; i++) {
            int j = i + len - 1;
            dp[i][j] = max(a[i] - dp[i+1][j], a[j] - dp[i][j-1]);
        }
    }

    // 输出结果
    cout << dp[1][n] << endl;

    return 0;
}

接下来用数据模拟展示：

假设输入数据为 5 2 7 8 1 2，那么初始化的 dp 数组为：

dp[1][1] = 2
dp[2][2] = 7
dp[3][3] = 8
dp[4][4] = 1
dp[5][5] = 2

接着，根据状态转移方程，依次计算 dp 数组的值：

dp[1][2] = max(2 - dp[2][2], 7 - dp[1][1]) = max(2 - 7, 7 - 2) = 5
dp[2][3] = max(7 - dp[3][3], 8 - dp[2][2]) = max(7 - 8, 8 - 7) = 1
dp[3][4] = max(8 - dp[4][4], 1 - dp[3][3]) = max(8 - 1, 1 - 8) = 7
dp[4][5] = max(1 - dp[5][5], 2 - dp[4][4]) = max(1 - 2, 2 - 1) = 1
dp[1][3] = max(2 - dp[2][3], 7 - dp[1][2]) = max(2 - 1, 7 - 5) = 2
dp[2][4] = max(7 - dp[3][4], 8 - dp[2][3]) = max(7 - 7, 8 - 1) = 7
dp[3][5] = max(8 - dp[4][5], 1 - dp[3][4]) = max(8 - 1, 1 - 7) = 7
dp[1][4] = max(2 - dp[2][4], 7 - dp[1][3]) = max(2 - 7, 7 - 2) = 5
dp[2][5]