1.题目介绍
给你一个整数数组 \(nums\) ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1]
输出：1
示例 3：
输入：nums = [5,4,-1,7,8]
输出：23
提示：
- \(1 <= nums.length <= 10^{5}\)
- \(-10^{4} <= nums[i] <= 10^{4}\)
进阶：如果你已经实现复杂度为 \(O(n)\) 的解法，尝试使用更为精妙的 分治法 求解。
2. 题解
2.1 动态规划
思路
这里关键点是保证每个f(i)均是从0->i所有组合中子数组和最大的组合，
那么便可以基于f(i)已是前面所有组合中最大的，来判断f(i+1),
若是f(i)+nums[i+1] < nums[i+1],便舍弃之前的组合，从这里开始新的子数组
同时使用一个标记来记录最大值
代码
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int pre = 0;
int maxAns = pre;
for (auto &x : nums){
pre = max(x, pre + x);
maxAns = max(maxAns, pre);
}
return maxAns;
}
};
2.2 分治
思路
代码
2.3
class Solution {
public int maxSubArray(int[] nums) {
int max = nums[0], sum = 0;
for (int item : nums) {
sum += item;
max = Math.max(max, sum);
if (sum < 0) {
sum = 0;
}
}
return max;
}
}