单选题 适中
#20417

给定一个整数数组 nums,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 下面横线处应该填入的是?( ) # include <io…

给定一个整数数组 nums,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

下面横线处应该填入的是?( )

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int maxSubArray(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;
    vector<int> dp(n, 0);
    dp[0] = nums[0];
    int maxSum = dp[0];
    for (int i = 1; i < n; i++) {
        _______________________________
        maxSum = max(maxSum, dp[i]);
    }
    return maxSum;
}
int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    int result = maxSubArray(nums);
    cout << result << endl;
    return 0;
}
未登录也能判分,登录后才会记录
答案与解析
正确答案:B
解析

dp[i] 表示以 i 结尾的最大子段和。如果 i-1 也在最大子段和中,对应 dp[i-1] + nums[i] ,否则只有 i 在最 大子段和,对应  nums[i] ,所以选择 B。(动态规划)