C++简单一维动态规划

当涉及到一维动态规划问题时，你可以使用一个一维数组来存储中间结果。下面是一个简单的示例，演示了如何使用一维动态规划解决最大子序列和问题（Maximum Subarray Sum Problem）：

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

int maxSubarraySum(std::vector<int>& nums) {
    int n = nums.size();
    std::vector<int> dp(n);  // 一维数组用于存储中间结果
    dp[0] = nums[0];  // 初始条件
    
    int maxSum = dp[0];  // 记录最大子序列和
    
    for (int i = 1; i < n; i++) {
        // 状态转移方程：dp[i] = max(dp[i-1] + nums[i], nums[i])
        dp[i] = std::max(dp[i-1] + nums[i], nums[i]);
        maxSum = std::max(maxSum, dp[i]);
    }
    
    return maxSum;
}

int main() {
    std::vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int maxSum = maxSubarraySum(nums);
    std::cout << "Maximum subarray sum: " << maxSum << std::endl;
    
    return 0;
}

这个示例中，我们使用了一个一维数组 dp 来存储中间结果，其中 dp[i] 表示以 nums[i] 结尾的最大子序列和。然后，我们通过迭代数组 nums，计算每个位置的最大子序列和，并更新 maxSum 来记录全局最大值。最后，我们返回 maxSum。

以上代码的输出结果为：

Maximum subarray sum: 6

表明最大的子序列和是 6，对应子序列为 {4, -1, 2, 1}。