PAT甲级——1007 Maximum Subsequence Sum (25分)-白红宇

PAT甲级——1007 Maximum Subsequence Sum (25分)

阅读量：794 次

发布时间：2023-02-26

本文共 1088 字，大约阅读时间需要 3 分钟。

为了解决这个问题，我们需要找到一个数组中的最大子序列和。这个子序列可以是任何长度，包括负数。我们可以使用动态规划的方法来优化到O(n)的时间复杂度。

方法思路

我们可以使用动态规划的方法来解决这个问题。具体步骤如下：

初始化：创建一个数组dp，其中dp[i]表示以i结尾的最长子序列的和。初始化dp[0]为数组的第一个元素。

维护最大值：维护一个变量max_so_far，记录当前以i结尾的子序列的和的最大值。

更新动态规划数组：对于每个元素i，计算dp[i]为max_so_far + a[i]。

更新最大值：在每一步中更新max_sum为当前最大的子序列和，并更新max_so_far为当前子序列和的最大值。

这种方法的时间复杂度为O(n)，适用于较大的数组。

解决代码

#include 
   
    
#include 
    
     
int main() {
    int n;
    std::cin >> n;
    std::vector
     
       a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }
    if (n == 0) return 0;
    
    std::vector
      
        dp(n);
    dp[0] = a[0];
    int max_so_far = dp[0];
    int max_sum = dp[0];
    
    for (int i = 1; i < n; ++i) {
        dp[i] = max_so_far + a[i];
        if (dp[i] > max_sum) {
            max_sum = dp[i];
        }
        if (dp[i] > max_so_far) {
            max_so_far = dp[i];
        }
    }
    
    return max_sum;
}