给你一个整数数组 请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。如果最大和小于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 ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。用滑动窗口怎么做

可以使用滑动窗口的思想来解决这个问题。定义两个指针left和right，分别指向子数组的左右边界，初始值都为0。同时定义一个变量maxSum表示最大和，一个变量curSum表示当前子数组的和，初始值都为nums。然后开始循环，每次将right指针向右移动一位，同时将curSum加上nums[right]，如果curSum大于maxSum，则更新maxSum的值。如果curSum小于等于0，则将left指针向右移动一位，同时将curSum减去nums[left]。重复上述过程直到right指针到达数组末尾。最后返回maxSum即可。

代码如下：

public int maxSubArray(int[] nums) {
    int left = 0, right = 0;
    int maxSum = nums[0], curSum = nums[0];
    while (right < nums.length - 1) {
        right++;
        curSum += nums[right];
        while (curSum <= 0 && left < right) {
            curSum -= nums[left];
            left++;
        }
        maxSum = Math.max(maxSum, curSum);
    }
    return maxSum;
}

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

解法一：暴力枚举

最直观的方法是枚举所有可能的连续子数组，计算它们的和，最后返回最大值。时间复杂度为 $O(n^2)$。

Python 代码

class Solution:
def maxSubArray(self, nums: List[int]) -> int:
n = len(nums)
ans = float('-inf')
for i in range(n):
sum = 0
for j in range(i, n):
sum += nums[j]
ans = max(ans, sum)
return max(ans, 0)

解法二：贪心算法

对于一个连续子数组，如果它的和小于 0，那么它对后面的子数组一定是减少贡献的，因此可以舍弃它，从下一个位置重新开始寻找连续子数组。这种贪心思想可以用一个变量 sum 记录当前连续子数组的和，如果 sum 小于 0，就将 sum 置为当前元素的值，否则将 sum 加上当前元素的值。在这个过程中，用一个变量 ans 记录最大的 sum 值，最后返回 ans 即可。

时间复杂度为 $O(n)$。

Python 代码

class Solution:
def maxSubArray(self, nums: List[int]) -> int:
n = len(nums)
ans = float('-inf')
sum = 0
for i in range(n):
if sum < 0:
sum = nums[i]
else:
sum += nums[i]
ans = max(ans, sum)
return max(ans, 0)

解法三：动态规划

设 dp[i] 表示以第 i 个元素为结尾的最大连续子数组和，则有转移方程：

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

解释：如果 dp[i-1] 大于 0，那么 dp[i] 就是 dp[i-1]+nums[i]，否则 dp[i] 就是 nums[i]。

最终的结果即为所有 dp[i] 中的最大值。

时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。

Python 代码

class Solution:
def maxSubArray(self, nums: List[int]) -> int:
n = len(nums)
dp = [0] * n
dp[0] = nums[0]
ans = dp[0]
for i in range(1, n):
dp[i] = max(dp[i-1]+nums[i], nums[i])
ans = max(ans, dp[i])
return max(ans, 0)