给你一个整数数组 请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。如果最大和小于0，则返回0. 子数组 是数组中的一个连续部分。

示例 1:

输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

示例 2:

输入: [-1,-2,-3,-4,-5]
输出: 0
解释: 所有子数组的和都小于0，因此返回0。

解法：

动态规划

定义状态：dp[i]表示以第i个元素结尾的最大子数组和

状态转移方程：dp[i] = max(dp[i-1]+nums[i], nums[i])

初始状态：dp[0] = nums[0]

最终结果：max(dp[0], dp[1], ..., dp[n-1])

class Solution {
public:
int maxSubArray(vector<int>& nums) {
if (nums.empty()) return 0;
int n = nums.size();
vector<int> dp(n);
dp[0] = nums[0];
int res = dp[0];
for (int i = 1; i < n; i++) {
dp[i] = max(dp[i-1]+nums[i], nums[i]);
res = max(res, dp[i]);
}
return res;
}
};

相关问题

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 子数组 是数组中的一个连续部分。

题目描述：给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

解题思路：使用动态规划的思想，定义一个数组dp，其中dp[i]表示以第i个元素结尾的最大子数组和。则有状态转移方程：dp[i] = max(dp[i-1]+nums[i], nums[i])。最终结果为dp数组中的最大值。

代码实现：

class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n, );
dp[] = nums[];
int res = dp[];
for(int i=1; i<n; i++){
dp[i] = max(dp[i-1]+nums[i], nums[i]);
res = max(res, dp[i]);
}
return res;
}
};

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

这个问题通常被称为“最大子数组和”（Maximum Subarray Sum），也可以称为 Kadane’s 算法。给定一个整数数组 `nums`，你需要计算其中连续子数组的最大和，可以是负数、零或正数。算法的主要步骤如下：

1. 初始化两个变量：`current_sum` 存储当前连续子数组的和，`max_sum` 存储到目前为止找到的最大和。初始化它们都为数组的第一个元素。

2. 遍历数组，对于每个元素：
- 如果当前元素加上 `current_sum` 大于0，则将当前元素加到 `current_sum` 上；否则，说明当前元素开始了一个新的负向子数组，所以从零开始更新 `current_sum`。
- 比较 `current_sum` 和 `max_sum`，如果 `current_sum` 更大，就更新 `max_sum`。

3. 当遍历完整个数组后，`max_sum` 就是最大连续子数组的和。

以下是 Python 代码示例：

def maxSubArray(nums):
    if not nums: return 0
    current_sum = max_sum = nums[0]
    
    for num in nums[1:]:
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)
        
    return max_sum